149_MaxPointsonaLine - a920604a/leetcode GitHub Wiki

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int ret = 0, n = points.size();
        for(int i=0;i<n;++i){
            map<pair<int,int> ,int> m;
            int duplicate = 1;
            for(int j = i+1;j<n;++j){
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                int d = gcd(dx, dy);
                m[{dx/d,dy/d}]++;
            }
            
            ret = max(ret, duplicate);
            for(auto it = m.begin() ; it!=m.end() ; ++it){
                ret = max(ret, it->second+duplicate);
            }
        }
        return ret;
        
        
    }
    int gcd(int a, int b){
        return (b==0)?a:gcd(b, a%b);
    }
};