부동점수 연산의 비교 크기에 관한 문제

3755 단어
LetCode에 코드를 썼습니다.
링크는 다음과 같습니다.https://leetcode.com/problems/erect-the-fence/#/description
운용완성
원래 간단한 프로그램인데 마지막에 AC가 안 돼요.
/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 * }
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct Point* outerTrees(struct Point* points, int pointsSize, int* returnSize) {
    double costhta(double x1, double y1, double x2, double y2);
    if(pointsSize == 1) 
    {
        *returnSize = 1;
        return points;
    }
    struct Point* ret;
    ret = (struct Point*)malloc(sizeof(struct Point)*(pointsSize+1));
    int i, j = 0, pushed, befpush;
    double theta, maxtheta, vectorx, vectory;
    ret[0].x = points[0].x;
    ret[0].y = points[0].y;
    pushed = 0;
    for(i = 1; i < pointsSize; i++)
    {
        if(points[i].x < ret[0].x) 
        {
            ret[j].x = points[i].x;
            ret[j].y = points[i].y;
            pushed = i;
        }
    }
    j++;
    befpush = pushed;
    pushed = 0;
    
    if(befpush == 0) pushed = 1;
    maxtheta = costhta(0, 1, (points[pushed].x - ret[j-1].x), (points[pushed].y - ret[j-1].y));
    ret[j].x = points[pushed].x;
    ret[j].y = points[pushed].y;
    
    for(i = 0; i < pointsSize; i++)
    {
        if(i == befpush || i == pushed) continue; 
        theta = costhta(0, 1, (points[i].x - ret[j-1].x), (points[i].y - ret[j-1].y));


        if(theta == maxtheta)
        {
            if(abs(points[i].x-ret[j-1].x) < abs(points[pushed].x - ret[j-1].x))
            {
            pushed = i;
            ret[j].x = points[i].x;
            ret[j].y = points[i].y;
            }
        }
        if(maxtheta < theta)
        {
            pushed = i;
            maxtheta = theta;
            ret[j].x = points[i].x;
            ret[j].y = points[i].y;
        }
    }
    j++;
  
    while(true)
    {
        vectorx = ret[j-1].x - ret[j-2].x;
        vectory = ret[j-1].y - ret[j-2].y;
        befpush = pushed;
        pushed = 0;
        if(befpush == 0) pushed = 1;
        maxtheta = costhta(vectorx, vectory, (points[pushed].x - ret[j-1].x), (points[pushed].y - ret[j-1].y));
        ret[j].x = points[pushed].x;
        ret[j].y = points[pushed].y;
        
        
        for(i = 0; i < pointsSize; i++)
        {
            if(i == befpush || i == pushed) continue; 
            theta = costhta(vectorx, vectory, (points[i].x - ret[j-1].x), (points[i].y - ret[j-1].y));
            if(fabs(theta - maxtheta) < 0.000000001)
            {
                if(abs(points[i].x-ret[j-1].x)+abs(points[i].y - ret[j-1].y) < abs(points[pushed].x - ret[j-1].x) + abs(points[pushed].y - ret[j-1].y))
                {
                pushed = i;
                ret[j].x = points[i].x;
                ret[j].y = points[i].y;
                }
            }
            if(theta - maxtheta > 0.00000001)
            {
                pushed = i;
                maxtheta = theta;
                ret[j].x = points[i].x;
                ret[j].y = points[i].y;
            }
        }
        if( (ret[j].x == ret[0].x) && (ret[j].y == ret[0].y) )
        {
            break;
        }
        if( maxtheta == -1)
        {
            printf("i
"); break; } j++; } *returnSize = j; return ret; } double costhta(double x1, double y1, double x2, double y2) { return (x2 * x1 + y1 * y2)/sqrt(x2*x2 + y2*y2)/sqrt(x1*x1 + y1*y1); }

나중에 문제의 관건은 크기를 거기에 비교하는 데 있다는 것을 발견했다.
부동점수의 크기를 비교하면 본래 같은 두 수를 가져야 하는데 계산 오차로 인해 둘이 다르기 때문에 더욱 심각한 것은 그 중 어느 곳에 문제가 판단되어 결과를 바꾸게 된다는 것이다.
그래서 앞으로 부동점수 비교 더블아 0.000001.

좋은 웹페이지 즐겨찾기