给定平面上的n个点，求最多有多少个点共线_如何求共线次数

给定一个二维平面上的n个点，找出同一条直线上的最大点数。
解法：
穷举，注意斜率不适用float作为键，精度损失。

class Solution {
public:
    int gcd(int x,int y) { //求最大公约数
        if (y == 0)
            return x;
        else
            return  gcd(y, x%y);
    }
    int maxPoints(vector<Point> &points) {
        if(points.empty())
            return 0;
        else if(points.size() <= 2)
            return points.size();
        sort(points.begin(), points.end(), [](Point a, Point b){return a.x<b.x;});
        long long ans = 0;
        int n = points.size();
        for(int i = 0; i < n; i++){
            map<pair<int, int>, long long> m;
            long long  cover = 0, vertical = 0, maxk = 0;
            for(int j = i+1; j<n; j++){
                int dx = points[i].x - points[j].x;
                int dy = points[i].y - points[j].y;
                if(dx == 0 && dy == 0)  //两点重合
                    ++cover;
                else if(dx == 0)      //两点横坐标相等（不重合）
                    maxk = max(maxk, ++vertical);
                else{
                    int g = gcd(dx, dy);
                    dx/=g, dy/= g;
                // 计算最大公约数：欧几里得算法
               // 斜率不适用float作为键，精度损失，使用除以最大公约数后的pair作为键
                    maxk = max(maxk, ++m[make_pair(dx, dy)]);
                }
            }
            ans = max(ans, maxk + cover +1);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39