short C++ solution by gcd


  • 0
    P
    class Solution {
    private:
        int gcd(int a, int b){
            if(b == 0) return a;
            return gcd(b, a % b);
        }
    public:
        int maxPoints(vector<Point>& points) {
            int res = 0;
            for(int i = 0; i < points.size(); i++){
                int dup = 1, localmax = 0;
                unordered_map<int, unordered_map<int, int>> m;
                for(int j = i + 1; j < points.size(); j++){
                    int dx =  points[i].x - points[j].x, dy = points[i].y - points[j].y;
                    if(dx == 0 && dy == 0) dup++;
                    else{
                        int g = gcd(dx, dy);
                        if(g != 0){
                            dx = dx / g;
                            dy = dy / g;
                        }
                        m[dx][dy]++;
                        localmax = max(localmax, m[dx][dy]);
                    }
                }
                res = max(res, localmax + dup);
            }
            return res;
        }
    };
    

Log in to reply
 

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