Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
大意为：给定二维平面的一组points，从中找出在同一直线上的最多的点的数量并返回
最直白最简单的算法是采用遍历法，用两层遍历，先从中选定一个点，再遍历所有的点，找出与其斜率相等的点，然后更新定义的maxNum。最后即得到答案。
大致步骤为：
1.第一层遍历选中一个点a(x1, y1)
2.第二层遍历所有的点b(x2,y2)，若
1）x1 = x2且 y1 = y2，将samepoints++(自己声明的变量，表示相同点的个数);
2）x1 = x2且y1 != y2, 将其斜率置为INT_MAX，并将其对应的点数加一
3）k = (float)(y1 - y2)/(x1 - x2),将k对应的点数加一
3.一次循环结束，更新maxNum = MAX（（K）对应的点数 + samepoints）
4.所有循环结束，返回maxNum即可。
/**
* Definition for a point. * struct Point { * int x; * int y; * Point() : x(0), y(0) {} * Point(int a, int b) : x(a), y(b) {} * }; *///自己声明的一个结构体
struct element { float k; int kNum; element():k(0.0), kNum(0){} }; class Solution { public: int maxPoints(vector<Point>& points) { int maxNum = 0; bool IsFind = false; for(int i= 0; i < points.size(); i++) { //同位置的点 int samePoint = 0; //存储元素 vector<struct element> kVec; for(int j = 0; j < points.size(); j++) { //同点 if(points[i].y == points[j].y && points[i].x == points[j].x) { samePoint++; } //无k else if(points[i].x == points[j].x) { for(int m = 0; m < kVec.size(); m++) { if(kVec[m].k == INT_MAX) { kVec[m].kNum++; IsFind = true; break; } } if(!IsFind) { struct element el; el.k = INT_MAX; el.kNum = 1; kVec.push_back(el); } else { IsFind = false; } } //正常情况 else { float k = (float)(points[j].y - points[i].y) / (points[j].x - points[i].x); for(int m = 0; m < kVec.size(); m++) { if(kVec[m].k == k) { kVec[m].kNum++; IsFind = true; break; } } if(!IsFind) { struct element el; el.k = k; el.kNum = 1; kVec.push_back(el); } else { IsFind = false; } } } if(kVec.empty()) return samePoint; //找最大的 for(int i = 0; i < kVec.size(); i++) { if(maxNum < kVec[i].kNum + samePoint) { maxNum = kVec[i].kNum + samePoint; } } } return maxNum; }};
1.本题虽然解出来了，但是有一定的局限，即假定了k没有取到INT_MAX(代码中将其作为K为无穷时的斜率)的取值，并且假定k在float的取值范围内。不过在LeetCode平台能通过，那就是满足题目要求。
2.本题还可以利用c++STL中的map来存储k对应点的个数，即声明一个map<float， int>的变量，详细解答及代码可参见博文