Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
[Analysis]
The points on a line share the same slope: i.e. if point (x,y) is on the line formed by point (x1, y1) and (x2, y2), (y-y1) / (x-x1) = (y2-y1)/(x2-x1). For a given point, explore each slope (with other points) then we can find the result.
Corner cases to consider: 1) duplicated points; 2) points in a horizontal line, i.e. x1 = x2.
[Solution]
class Solution {
public:
int maxPoints(vector<Point> &points) {
if (points.size()<3) return points.size();
int num = 2;
for (int i=0; i<points.size(); i++) {
unordered_map<float, int> slopes;
int horizonal_cnt =0;
int same_points = 1;
for (int j=i+1; j<points.size(); j++) {
if (points[j].x == points[i].x && points[j].y == points[i].y) {
same_points ++;
}
else
if (points[j].x == points[i].x) {
horizonal_cnt++;
}
else {
float sl = (float) (points[j].y - points[i].y) / (points[j].x - points[i].x);
slopes[sl] ++;
}
}
num = max(num, same_points);
num = max(num, horizonal_cnt + same_points);
for (auto pair: slopes) {
num = max(num, pair.second + same_points);
}
}
return num;
}
};
No comments:
Post a Comment