Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Have you met this question in a real interview?
Example
Given 4 points: (1,2), (3,6), (0,0), (1,3).
The maximum number is 3.
LeetCode上的原题，请参见我之前的博客Max Points on a Line。
解法一：
class Solution {
public:
/**
* @param points an array of point
* @return an integer
*/
int maxPoints(vector<Point>& points) {
int res = , n = points.size();
for (int i = ; i < n; ++i) {
int duplicate = ;
unordered_map<double, int> m;
for (int j = i + ; j < n; ++j) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
++duplicate;
} else if (points[i].x == points[j].x) {
++m[INT_MAX];
} else {
double slope = (double)(points[j].y - points[i].y) / (points[j].x - points[i].x);
++m[slope];
}
}
res = max(res, duplicate);
for (auto it : m) {
res = max(res, it.second + duplicate);
}
}
return res;
}
};
解法二：
class Solution {
public:
/**
* @param points an array of point
* @return an integer
*/
int maxPoints(vector<Point>& points) {
int res = , n = points.size();
for (int i = ; i < n; ++i) {
int duplicate = ;
map<pair<int, int>, int> m;
for (int j = i + ; j < n; ++j) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
++duplicate; continue;
}
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int d = gcd(dx, dy);
++m[{dx / d, dy / d}];
}
res = max(res, duplicate);
for (auto it : m) {
res = max(res, it.second + duplicate);
}
}
return res;
}
int gcd(int a, int b) {
return (b == ) ? a : gcd(b, a % b);
}
};
解法三：
class Solution {
public:
/**
* @param points an array of point
* @return an integer
*/
int maxPoints(vector<Point>& points) {
int res = ;
for (int i = ; i < points.size(); ++i) {
int repeat = ;
for (int j = i + ; j < points.size(); ++j) {
int cnt = ;
int x1 = points[i].x, y1 = points[i].y;
int x2 = points[j].x, y2 = points[j].y;
if (x1 == x2 && y1 == y2) {++repeat; continue;}
for (int k = ; k < points.size(); ++k) {
int x3 = points[k].x, y3 = points[k].y;
if (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 == ) {
++cnt;
}
}
res = max(res, cnt);
}
res = max(res, repeat);
}
return points.empty() ? : res;
}
};