[LeetCode] Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

At first my thought was, given 2 points, we can get a line which connect these two points, and this line can be designated as:

y =  k x + b

Assume one of the two points is at (0, 0), so the other point is at (x2 – x1, y2 – y1), now, the only thing we need to do is calculate k value (slope of line). By calculating the k value of each two points, we get the most amount of same k value.

However, using slope of line has kind of trouble, that is, when x1 is equal to x2, x2 – x1 is zero, we can not divide something by zero, so in this particular situation, the slope of this line is infinite big. Additionally, we need to deal with situation that two points are at same position.

Finally, I used gcd of (x2 – x1) and (y2 – y1) to deal with this problem, if gcd is zero, means these two points are at same position; besides, I used hash map to save the “slope like thing”, and it can accelerate search speed.

 

    int gcd(int a, int b){
        return a ? a / abs(a) * abs(gcd(b % a, a)) : b;
    }

    int maxPoints(vector<Point> &points) {
        int result = 0;
        for(int i=0;i<points.size();i++){
            unordered_map<string,int> count;
            int same = 1;
            int mx = 0;
            for(int j = i + 1; j < points.size(); j ++){
                int x = points[i].x - points[j].x;
                int y = points[i].y - points[j].y;
                int g = gcd(x, y);
                if(!g){
                    same ++;
                    continue;
                }
                x /= g;
                y /= g;
                mx = max(mx, ++ count[to_string(x) + " " + to_string(y)]);
            }
            result = max(result, mx + same);
        }
        return result;
    }

🙂

This entry was posted in Algorithm, LeetCode and tagged , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*