Given n points
on a 2D plane, find the maximum number of points that lie on the same straight line.
O(n^2)， n次n条直线的便利，每次n条直线遍历都计算当前循环内落点最多的直线是哪条。
--------------
/**
* 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) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int cnt = points.size();
int samePoint = 0;
int vertical = 0;
unordered_map<double, int> slopeMap;
int ret = 0;
for (int i = 0; i < cnt; i++) {
samePoint = 1;
vertical = 0;
slopeMap.clear();
int x1 = points[i].x, y1 = points[i].y;
int maxslope = 0;
for (int j = 0; j < cnt; j++) {
if (i == j) continue;
int x2 = points[j].x;
int y2 = points[j].y;
if (x1 == x2) {
if (y1 == y2) {
samePoint++;
} else {
vertical++;
}
}
double slope = (double)(y2 - y1) / (double)(x2 - x1);
slopeMap[slope] += 1;
maxslope = max(maxslope, slopeMap[slope]);
}
ret = max(ret, max(vertical, maxslope) + samePoint);
}
return ret;
}
}