[LeetCode OJ] 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.

 

//定义二维平面上的点
struct Point
{
    int x;
    int y;
    Point(int a=0, int b=0):x(a),y(b){}
};
bool operator==(const Point& left, const Point& right)
{
    return (left.x==right.x && left.y==right.y);
}

//求两个点连接成的直线所对应的斜率
double line_equation(const Point& P1, const Point& P2)
{
    double slope;
    if(P1.x==P2.x)
        slope = 1e+6;
    else
        slope = double(P1.y-P2.y)/(P1.x-P2.x);
    return slope;
}

class Solution {
public:
    int maxPoints(vector<Point> &points) 
    {
        int max=0;
        for(vector<Point>::iterator it=points.begin(); it!=points.end(); ++it)
        {
            map<double, int> Line_count;
            int same_count=0;    //same_count表示同一个点重复出现的个数
            
            for(vector<Point>::iterator it2=it; it2!=points.end(); ++it2)   //此处it2=points.begin()还是it2=it虽然不影响最终结果，但是对于时间复杂度影响很大，it2=it的时间复杂度要低很多
            {
                if(*it==*it2)
                {
                    ++same_count;
                    continue;
                }    
                double slope = line_equation(*it, *it2);
                ++Line_count[slope];
            }
            set<int> iset;
            for(map<double, int>::iterator iter = Line_count.begin(); iter!=Line_count.end(); ++iter)
                iset.insert(iter->second);
            int max_now = same_count;
            if(iset.begin()!=iset.end())
                max_now = same_count + *(--iset.end());
            if(max_now>max)
                max = max_now;
        }
        return max;
    }
};

 

问题描述：在一个二维平面上有n个点，求出现在同一直线上的点的最大个数

分析：对每一个点计算与其他点（不包括与该点相同的点）连接成的直线的斜率，斜率重复出现的最大次数加成该点重复出现的个数，即为该点所在直线上拥有的最大点个数（比如该点既出现在直线L1上，又出现在直线L2上，直线L1上有这n个点中的3个点，直线L2上有这n个点中的5个点，我们得到的该点所处直线的拥有最多点的那一条直线上的点个数便是5，有点绕口~~）。

对每一个点进行相同的操作，便可得到n个点中出现在同一直线的点的最大个数。

只需考虑斜率就可以解决这个问题，之前考虑还需要截距，其实完全不必要，不要把问题想得太复杂~