149 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.

Solution

/**
 * 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 {
public:
    long gcd(long a, long b) {
        long x = min(a, b), y = max(a, b);
        if ( y%x == 0 ) return x;
        return (gcd(x, y-x));
    }
    string getLine(Point p1, Point p2) {
        // Ax + By + C = 0
        int x1 = p1.x, x2 = p2.x, y1 = p1.y, y2 = p2.y;
        if ( x1 == x2 ) return "1, 0, " + to_string(-x1);
        if ( y1 == y2 ) return "0, 1, " + to_string(-y1);
        long A = abs(y2-y1);
        long i = abs(y2-y1)/(y2-y1);
        long B = (x1-x2)*i, C = (x2*y1 - x1*y2)*i;
        i = gcd(A, abs(B));
        if ( C == 0 ) return to_string(A/i) + ", " + to_string(B/i) + ", 0";
        i = gcd(i, abs(C));
        return to_string(A/i) + ", " + to_string(B/i) + ", " + to_string(C/i);
    }
    int maxPoints(vector<Point>& points) {
       unordered_map<string, unordered_set<int>> lines;
       int n = points.size(), npoints = 1;
       if ( n <= 2 ) return n;
       vector<int> count(n, 1);
       for ( int i = 0; i < n-1; i++ ) {
           for ( int j = i+1; j < n; j++ ) {
               if ( points[j].x == points[i].x and points[j].y == points[i].y ) {
                   count[i] += 1;
                   count[j] += 1;
                   npoints = max(max(npoints, count[i]), count[j]);
                   continue;
               }
               string line = getLine(points[j], points[i]);
               if ( lines.find(line) == lines.end() or lines[line].find(i) == lines[line].end() ) lines[line].insert(i);
               if ( lines.find(line) == lines.end() or lines[line].find(j) == lines[line].end() ) lines[line].insert(j);
               npoints = max(npoints, int(lines[line].size()));
           }
       }
       return npoints;
    }
};

Notes

• The key point is how to use a "hashable" variable to represent a line. vector, pair, cannot used as the key in a hashMap.
• Note the specialty of "same points".