Share C++ clean solution using pairing function


  • 0
        int maxPoints(vector<Point>& points) {
            unordered_map<long, int> count;
            int n = points.size(), _max = 0;
            for (int i = 0; i < n; ++i) {
                int dup = 1, maxNoDup = 0;
                for (int j = i + 1; j < n; ++j) {
                    int a = points[j].y - points[i].y, b = points[j].x - points[i].x;
                    if (a == 0 && b == 0) { dup++; continue; }
                    int g = gcd(a, b);
                    long key = hash(a / g, b / g) * n + i;
                    maxNoDup = max(maxNoDup, ++count[key]);
                }
                _max = max(_max, maxNoDup + dup);
            }
            return _max;
        }
        
        long hash(long a, long b) {               // Z x Z -> N
            a = abs(a) * 2 - (a < 0);             // Z -> N
            b = abs(b) * 2 - (b < 0);
            return (a + b + 1) * (a + b) / 2 + a; // pairing function: N x N -> N
        }
        
        int gcd(int a, int b) {
            if (b == 0) return a;
            return gcd(b, a % b);
        }
    

Log in to reply
 

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