Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
---------------------------------------------------------------------------------
O(n^2)
/**
* 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 maxP = 2;
if (points.size() == 0 || points.size() == 1) return points.size();
for (int i = 0; i < points.size(); i++) {
unordered_map<double,int> slopes;
int samex = 1;
int samePoints = 0;
int curMax = 0;
for (int j = i + 1; j < points.size(); j++) {
double xdistance = points[i].x - points[j].x;
double ydistance = points[i].y - points[j].y;
if (xdistance == 0 && ydistance == 0) {
samePoints++;
continue;
}else if (xdistance == 0) {
samex++;
continue;
}
double slope = ydistance / xdistance;
if (slopes.find(slope) == slopes.end()) {
slopes[slope] = 2;
}else {
slopes[slope]++;
}
curMax = max(curMax,max(samex,slopes[slope]));
}
curMax = max(samex,curMax);
maxP = max(maxP,curMax + samePoints);
}
return maxP;
}
};