Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
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 = 0, n = points.size(); for (int i = 0; i < n; ++i) { int duplicate = 1; unordered_map<double, int> m; for (int j = i + 1; 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 = 0, n = points.size(); for (int i = 0; i < n; ++i) { int duplicate = 1; map<pair<int, int>, int> m; for (int j = i + 1; 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 == 0) ? a : gcd(b, a % b); } };
解法三：
class Solution { public: /** * @param points an array of point * @return an integer */ int maxPoints(vector<Point>& points) { int res = 1; for (int i = 0; i < points.size(); ++i) { int repeat = 1; for (int j = i + 1; j < points.size(); ++j) { int cnt = 0; 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 = 0; 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 == 0) { ++cnt; } } res = max(res, cnt); } res = max(res, repeat); } return points.empty() ? 0 : res; } };
本文转自博客园Grandyang的博客，原文链接：共线点个数Max Points on a Line ，如需转载请自行联系原博主。
