每日leetcode-149

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.

这道题直接用最简单的$n^3$的遍历就可以做，但是有几点没有注意：

1. 固定第一个、第二个点，确定其他点是不是共线的时候，需要注意前两个点不能相同！
2. 可能所有点都是相同的！也就是两个点、三个点的时候，都是相同的点！
3. 不能在相同的时候直接判断下一个是否相同然后累计连续的相同的点的个数！因为可能会前面也有别的相同的点！所以不要直接用计数变量的方式处理这种情况，要单独写一个记录当前相同点数目的！

class Solution {
public:
    bool isSameLine(vector<int>& a, vector<int>& b, vector<int>& c) {
        // k = (a[1] - b[1]) / (a[0] - b[0]) = (a[1] - c[1]) / (a[0] - c[0])
        return (long long)(a[0] - b[0]) * (long long)(a[1] - c[1]) == (long long)(a[1] - b[1]) * (long long)(a[0] - c[0]);
        // 都不为0时，没有问题；为0时，分别是三个横坐标/纵坐标相等或者两个点重合
    }
    
    int maxPoints(vector<vector<int>>& points) {
        int len = points.size();
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return 1;
        }
        int ans = 2;
        int count;
        for (int i = 0; i < len - 2; i++) {
            int same_points = 0;
            for (int j = i + 1; j < len; j++) {  // 可能有三个点相同的情况
                if (points[i] == points[j]) {
                    same_points++;
                    continue;
                }
                count = 2;
                for (int k = j + 1; k < len; k++) {
                    if (isSameLine(points[i], points[j], points[k])) {
                        count++;
                    }
                }
                if (count + same_points > ans) {
                    ans = count + same_points;
                }
            }
            if (1 + same_points > ans) {
                ans = 1 + same_points;
            }
        }
        
        return ans;
    }
};