Description

Submission

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        int ret = 0;

        for(int i = 0; i < n; ++i) {
            map<pair<int, int>, int> count;
            int same = 0;
            int vertical = 0;
            for(int j = 0; j < n; ++j) {
                if(i == j) continue;
                if(points[i] == points[j]) {
                    ++same;
                    continue;
                }
                int dy = points[j][1] - points[i][1];
                int dx = points[j][0] - points[i][0];

                if(dx == 0) {
                    ++vertical;
                    continue;
                }
                ++count[make_pair(dy/gcd(dy, dx), dx/gcd(dy, dx))];
            }

            for(auto x: count) {
                ret = max(ret, x.second + same + 1);
            }

            ret = max(ret, vertical + same + 1);
        }
        return ret;
    }
};

// fix one point, traverse all the other points and calculate slope