地址

https://leetcode.com/problems/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.

思路

直线可以用y=kx+b表示，<k,b>可以表示一条直线。如果我们求过点P的直线，那么只用斜率k就可以表示出来了，b可以不用管。

法一：我们可以用map<double, int>来求有多少个相同的k。但求斜率k=(y2-y1)/(x2-x1)时有浮点误差，直接比较不可行。注意到题目中所有点的坐标都是整数，所以斜率k=(y2-y1)/(x2-x1)可以化简成分数表示，将分子分母同除两者的gcd，则可以使用<ny,nx>来表示k。

法二：不使用map来统计，使用数组记录所有的k=(y2-y1)/(x2-x1)。然后对数组sort一遍，从左到右扫描一遍数组统计即可。统计时判断相等用abs(x-y) < eps来处理。

代码

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        map<pair<int,int>, int>hs;
        int ans = 0;
        for(int i = 0, n = points.size(); i < n; ++i)
        {
            hs.clear();
            int cnt = 0, x, y, d, same=1;
            for(int j = i + 1; j < n; ++j)
            {
                x = 0, y = 1e9;
                if(points[i] == points[j])
                {
                    same+=1;
                    continue;
                }
                d = __gcd(points[j][1] - points[i][1], points[j][0] - points[i][0]);
                x = (points[j][1] - points[i][1]) / d;
                y = (points[j][0] - points[i][0]) / d;
                cnt = max(cnt, ++hs[make_pair(x,y)]);
                //cout<<k<<" "<<hs[k]<<endl;
            }
            ans = max(ans, cnt+same);
        }
        return ans;
    }
};