leetcode每日一道（3）最多能有多少个点位于同一直线上

题目

对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一直线上
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

思路

复杂度肯定是o(n^2)的，即两层遍历可以完成任务。那么最大的问题的就是如何实现了，需要考虑的有如下几点：

• 1.在第一层遍历时，给定一个点i，再遍历剩余的点，这些点一旦和给定点的斜率是一样的，那么肯定是处于一条直线中，所有思路是可以建立一个哈希表，即建立一个以斜率为键，共线的点的数目为值的映射表；
• 2.要考虑重复的点；
• 3.最后共线的点的数目是最大共现数目加上重复的点数目；
• 4.要考虑垂直的点，斜率不存在的情况，单独拎出来讨论；
• 5.有些同学说斜率k无法唯一确定直线，这是因为要考虑截距。我们这里是针对一个定点而言，其他的点和这个定点的斜率如果一致，当然是可以确定处于同一条直线上。

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int n = points.size();
        if (n==0) return 0;
        else if (n==1) return 1;
        int max_value = 0;
        for (int i=0;i<n;i++){
            int repeat = 0;
            int vertical = 0;
            map<double,int> mp;
            int curmax = 1;
            for(int j=0;j<n;j++){
                if (i !=j){
                    double delta_x = points[j].x - points[i].x;
                    double delta_y = points[j].y - points[i].y;
                    if (delta_y == 0 && delta_x== 0) {
                        repeat +=1;
                        
                    }
                    else if (delta_x ==0) {
                        if (vertical ==0)
                        vertical =2;
                        else{
                            vertical +=1;
                        }
                        curmax = max(vertical, curmax);
                    }
                    else{
                        double k = delta_y/delta_x;
                        if (mp[k]==0) {
                            mp[k] =2;
                            curmax = max(mp[k],curmax);
                        }
                        else{
                            mp[k] += 1;
                            curmax = max(mp[k],curmax);
                        }
                    }
                }
            }
            max_value = max(max_value, curmax+repeat);
        }
        return max_value;
    }
};