149_maxPoints.txt

class Solution {
public:
    int gcd(int a, int b) {
        return b ? gcd(b, a % b) : a;
    }
    int maxPoints(vector<vector<int>>& points) {
        int len = points.size();
        if(len < 3)
            return len;
        int res = 0;
        for(int i = 0;i<len;i++){
            //如果当前结果大于点总数的一半 或 大于剩下的所有点
            if(res > len-i || res > len/2)
                break;
            unordered_map<int,int> count;
            for(int j = i+1;j<len;j++){
                int x = points[i][0]-points[j][0];
                int y = points[i][1]-points[j][1];
                if(x==0)
                    y = 1;
                else if(y==0)
                    x = 1;
                else{
                    if(y < 0){
                        x = -x;
                        y = -y;
                    }
                    int gcdXY = gcd(abs(x), abs(y));
                    x /= gcdXY;
                    y /= gcdXY;
                }
                count[y + x * 20001]++;
            }
            int maxn = 0;
            for (auto& [_, num] : count) {
                maxn = max(maxn, num + 1);
            }
            res = max(res, maxn);
        }
        return res;
    }
};