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.
点和方向确定一条直线。
需要两重循环，第一重循环遍历起始点a，第二重循环遍历剩余点b。
a和b如果不重合，就可以确定一条直线。
对于每个点a，构建 斜率->点数 的map。
(1)b与a重合，以a起始的所有直线点数+1 (用dup统一相加)
(2)b与a不重合，a与b确定的直线点数+1
/**
* 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) {
if(points.empty())
return ;
else if(points.size() == )
return ; int ret = ;
for(int i = ; i < points.size(); i ++)
{//start point
int curmax = ; //points[i] itself
unordered_map<double, int> kcnt; // slope_k count
int vcnt = ; // vertical count
int dup = ; // duplicate added to curmax
for(int j = ; j < points.size(); j ++)
{
if(j != i)
{
double deltax = points[i].x - points[j].x;
double deltay = points[i].y - points[j].y;
if(deltax == && deltay == )
dup ++;
else if(deltax == )
{
if(vcnt == )
vcnt = ;
else
vcnt ++;
curmax = max(curmax, vcnt);
}
else
{
double k = deltay / deltax;
if(kcnt[k] == )
kcnt[k] = ;
else
kcnt[k] ++;
curmax = max(curmax, kcnt[k]);
}
}
}
ret = max(ret, curmax + dup);
}
return ret;
}
};