20ms 80% O(n^2) C++ Solution with explanation


  • 2

    The key is to describe a straight line with a unique tuple ( a, b, c), which represents a line in coordinate system: ax + by + c = 0, that's why I introduce a struct Line for this purpose.

    To make the tuple (a, b, c) unique, we will have to make the three numbers not reducible, so we need to calculate the most common divisor of them. And note, we also have to make the variable "a" positive, otherwise (a, b, c) and (-a, -b, -c) will be regarded as two different lines.

    After that, nothing special, we iterate pairs of points in the set, calculate the representative tuples for the lines and add them to the map. When this is done, we have a line with the most time of occurrences. Then we check all points with that line, see if ax + by + c == 0.

    struct Line {
        int a, b, c;
        Line() : a(0), b(0), c(0) {};
        Line(int a, int b, int c) : a(a), b(b), c(c) {}
        size_t hashcode() {return ( (hash<int>()(a)) ^ ((hash<int>()(b) <<1) >>1) ^ (hash<int>()(c) <<1));}
    };
    
    class Solution {
    private: 
        int mcd( int a, int b ) {
            return b == 0 ? a : mcd( b, a%b );
        }
    
        bool getline( Point& p1, Point& p2, Line& line ) {
            if( p1.x == p2.x && p1.y == p2.y ) return false;
            if( p1.y == p2.y ) {
                line.a = 0; line.b = 1; line.c = -p1.y;
            } else if( p1.x == p2.x ) {
                line.a = 1; line.b = 0; line.c = -p1.x;
            } else {
                int aa = p1.y - p2.y, bb = p2.x - p1.x, cc = p1.x*p2.y - p2.x*p1.y;
                int cd = mcd( aa, mcd( bb, cc ) );
                aa /= cd; bb /= cd; cc /= cd;
                if( aa < 0 ) { aa = -aa; bb = -bb; cc = -cc; }
                line.a = aa; line.b = bb; line.c = cc;
            }
            return true;
        }
    public:
        int maxPoints(vector<Point>& points) {
            if( points.empty()) return 0;
            unordered_map<size_t, int> lines;
            Line target, l;
            int numline = 0, tmp, ans = 0;
            for( int i=0; i<points.size(); i++ ) {
                for( int j=i+1; j<points.size(); j++ ) {
                    if(!getline(points[i], points[j], l)) continue;
                    tmp = ++lines[l.hashcode()];
                    if( numline < tmp ) {
                        numline = tmp;
                        target = l;
                    }
                }
            } 
            for( Point p : points ) {
                if( target.a * p.x + target.b * p.y + target.c == 0 ) ans++;
            }
            return ans;
        }
    };

Log in to reply
 

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