（leetcode）Max Points on a Line

Question:

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

分析：

1、二维空间的任何一条线都可以表示成为y= k x + b 的形式。两点确定一条直线。固定其中一个点，遍历其余的点，斜率一致的即共线。

2、求斜率时只需遍历当前点与之后的点即可。

3、这里还要考虑斜率不存在的线。

4、还需要统计与当前固定点相同的点的个数。

5、内层遍历完毕即可求出过当前点的线的maxpoints.

6、外层循环遍历所有的点，即求出过所有点的maxpoints。maxpoints 中 的最大值即为所求。

code:

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
#define INF 10000000
class Solution {
public:
int maxPoints(vector<Point> &points)
{
    map<double,int> k_slope;//计算斜率相等的点的个数
    double k;
    int n;
    int MAX = 0;
    int rex_MAX = 0;
    map<double,int>::const_iterator C_it;//= k_slope.begin();
    for(int i = 0;i<points.size();i++)
    {
        n= 0;
        k_slope.clear();
        MAX = 0;
        for(int j = i+1;j<points.size();j++)
        {
            if(points[i].x!=points[j].x)
            {
                k = (double)(points[i].y-points[j].y)/(points[i].x-points[j].x);
            }
            else if(points[i].y==points[j].y)
            {
                n++;//与i点相同的点
                continue;
            }
            else//x相等，y不相等
                {
                k=INF;
            }

            k_slope[k]++;
        }
        C_it = k_slope.begin();
        for(;C_it!= k_slope.end();C_it++)//取最大值
        {
            if(MAX<C_it->second)
            MAX = C_it->second;
        }
        MAX += n+1;//加上重复的点n以及自身这个点。
        if(rex_MAX<MAX)
            rex_MAX = MAX;
    }
    return rex_MAX;//如果points为空返回0，否则即为max points。

}

};

（leetcode）Max Points on a Line,布布扣,bubuko.com

（leetcode）Max Points on a Line

原文：http://blog.csdn.net/zhangyuehuan/article/details/23763073