LeetCode 149. Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

解析：给定二维平面上的一组点，获取位于同一条直线上的点的最大数量。验证两个点在同一直线上，只需要验证斜率是否相等即可，同时要注意重合的点。采用map记录，key是两个点的斜率，value是出现的次数。

由于通过斜率来判断共线需要用到除法，而用 double 表示的双精度小数在有的系统里不一定准确，为了更加精确无误的计算共线，应当避免除法，从而避免无线不循环小数的出现，那么怎么办呢，这里把除数和被除数都保存下来，不做除法，但是要让这两数分别除以它们的最大公约数，这样例如8和4，4和2，2和1，这三组商相同的数就都会存到一个映射里面，同样也能实现目标。代码如下：

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

参考：

https://www.cnblogs.com/grandyang/p/4579693.html