Correct Answer on Xcode, but Wrong Answer on OJ


  • 0
    H
    class Solution {
    private:
        static bool equal(const Point & a, const Point & b) {
            return (a.x == b.x && a.y == b.y);
        }
        static double slope(const Point & a, const Point & b) {
            if (equal(a, b))
                return -std::numeric_limits<double>::infinity();
            else if (a.x == b.x)
                return std::numeric_limits<double>::infinity();
            else if (a.y == b.y)
                return 0.0;
            else
                return (a.y - b.y) / (double) (a.x - b.x);
        }
        struct Less_slope {
            Point ref;
            Less_slope(Point & p) {
                ref = Point(p.x, p.y);
            }
            bool operator() (const Point & p1, const Point & p2) {
                return slope(ref, p1) < slope(ref, p2);
            }
        };
        
    public:
        int maxPoints(vector<Point> &points) {
            if (points.size() < 2) {
                return (int)points.size();
            }
            int max_num = 2;
            for (int i = 0; i < points.size() - max_num; i++)
            {
                int duplicate = 0;
                int local_max = 2;
                std::sort(points.begin()+i+1, points.end(), Less_slope(points[i]));
                for(int j = i+1; j < points.size()-1; j++)
                {
                    if (equal(points[i], points[j])) {
                        //duplicate points
                        duplicate ++;
                        continue;
                    }
                    
                    double slope1 = slope(points[i], points[j]);
                    double slope2 = slope(points[i], points[j+1]);
                    
                    if (slope2 != slope1) {
                        //Not on the same line
                        continue;
                    }
                    
                    int count = 3;
                    j += 2;
                    while (j < points.size() && slope(points[i], points[j]) == slope1) {
                        j++;
                        count ++;
                    }
                    j--;
                    if (count > local_max) local_max = count;
                }
                
                local_max += duplicate;
                if (local_max > max_num) max_num = local_max;
            }
            
            return max_num;
        }
    };
    

    I failed to pass the following test on OJ:

    [(84,250),(0,0),(1,0),(0,-70),(0,-70),(1,-1),(21,10),(42,90),(-42,-230)]

    It said that my output was 3 but the correct answer is 6.

    However, when I tested on my laptop, the output was exactly 6. Here are my codes for testing:

    #include <cstdio>
    #include <algorithm>
    #include <limits>
    #include <vector>
    using namespace std;
    
    //Definition for a point.
    struct Point {
          int x;
          int y;
          Point() : x(0), y(0) {}
          Point(int a, int b) : x(a), y(b) {}
     };
    
    class Solution {...};
    
    int main()
    {
        vector<Point> input;
        int n;
        scanf("%d", &n);
        
        int x, y;
        while (n--) {
            scanf("%d", &x);
            scanf("%d", &y);
            input.push_back(Point(x,y));
        }
        
        printf("%d\n", Solution().maxPoints(input));
        
        return 0;
    }
    

    The input format is:

    9

    84 250

    0 0

    1 0

    0 -70

    0 -70

    1 -1

    21 10

    42 90

    -42 -230

    I ran the codes on ideone.com as well, and the output was also:

    6

    Can anyone tell me why is the output on OJ different from the output of my own testing?


  • 0
    M
    This post is deleted!

  • 0
    Q

    same here, run the things local can get right result


  • 0

    Here are the two places I found in your code which compares doubles directly:

    1. if (slope2 != slope1)
    2. slope(points[i], points[j]) == slope1

    You should never compare two doubles directly as that would lead to different precision error depending on machines and operating systems.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.