149. Max Points on a Line

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

c++

class Solution {
    int gcd(int p, int q) {
        return !q ? p : gcd(q, p % q);
    }
    pair<int, int> getInclinations(vector<int>& a, vector<int>& b) {
        int dx = a[1] - b[1];
        int dy = a[0] - b[0];
        if(!dx) return {1, 0};
        if(!dy) return {0, 1};
        int sign = dx * dy < 0 ? -1 : 1;
        dx = abs(dx), dy = abs(dy);
        int GCD = gcd(dx, dy);
        return {sign * dy / GCD, dx / GCD};
    }
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 1;
        for(int i = 0; i < n; i++) {
            map<pair<int, int>, int> table;
            for(int j = i + 1; j < n; j++) {
                pair<int, int> inc = getInclinations(points[i], points[j]);
                res = max(res, ++table[inc] + 1);
            }
        }

        return res;
    }
};