Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
[LeetCode Source]
思路：对每个节点求和其它节点的斜率，用hash_map统计斜率同样的点数。时间O(N^2)，空间O(N)。应该有更简单能够在O(1)空间的算法。临时没想出来。
这道题目AC率低的原因是因为各种边界条件，要注意：
1）有反复点的情况；
2）点数少于2的情况。
3）有垂直点（斜率为无穷）的情况。
遍历节点时注意已经遍历的节点不用再遍历了，避免反复遍历。
比方已经对前i个节点求了最大值，对第i+1个节点就不用再遍历前i个节点算斜率。由于之前节点已经对i+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) {
int size = points.size();
if(size<=1)
return size;
int res = 0;
for(int i=0;i<size;++i){
int local = 1;
int Vertical = 0;
int Dup = 0;
double k= 0.0;
unordered_map<double,int> map;
for(int j=i+1;j<size;++j){ //仅仅需对i+1大的值的点求线，由于以之前为小于i+1起点的直线已经遍历过i+1点，再求解就是反复遍历了
if(points[i].x == points[j].x){
if(points[i].y == points[j].y)
Dup++; //统计反复的点数
else
Vertical++; //统计水平的点数
}
else{
k = (points[j].y-points[i].y)*1.0/(points[j].x-points[i].x);
map[k]==0?map[k]=2:map[k]++; //计算在同一直线上的点 local = max(local,map[k]); //和该节点在同一直线上的最大点数 } } local = max(local+Dup,Vertical+Dup+1);//该节点加上反复的节点。注意水平和反复节点有可能是最大值 res = max(local,res);//计算全部解中的最大的节点 } return res; } };