Problem:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Idea:
count by slope
Time complexity: O(n^2)
Space complexity: O(n)
Solution:
C++ / pair
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// Author: Huahua // Running time: 6 ms class Solution { public: int maxPoints(vector<Point>& points) { int n = points.size(); int ans = 0; for (int i = 0; i < n; ++i) { std::map<std::pair<int,int>, int> count; int same_points = 1; int max_points = 0; for (int j = i + 1; j < n; ++j) { const Point& p1 = points[i]; const Point& p2 = points[j]; if (p1.x == p2.x && p1.y == p2.y) ++same_points; else max_points = max(max_points, ++count[getSlope(p1, p2)]); } ans = max(ans, same_points + max_points); } return ans; } private: // slope dy/dx : <dy, dx> std::pair<int, int> getSlope(const Point& p1, const Point& p2) { const int dx = p2.x - p1.x; const int dy = p2.y - p1.y; // horizontal line if (dy == 0) return { p1.y, 0 }; // vertical line if (dx == 0) return { 0, p1.x }; const int d = gcd(dx, dy); return { dy / d, dx / d }; } int gcd(int m, int n) { return n == 0 ? m : gcd(n, m % n); } }; |
C++ / long
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
// Author: Huahua // Running time: 4 ms class Solution { public: int maxPoints(vector<Point>& points) { int n = points.size(); int ans = 0; for (int i = 0; i < n; ++i) { unordered_map<long, int> count; int same_points = 1; int max_points = 0; const Point& p1 = points[i]; for (int j = i + 1; j < n; ++j) { const Point& p2 = points[j]; if (p1.x == p2.x && p1.y == p2.y) ++same_points; else max_points = max(max_points, ++count[getSlope(p1, p2)]); } ans = max(ans, same_points + max_points); } return ans; } private: // slope dy/dx : dy << 32 | dx long getSlope(const Point& p1, const Point& p2) { const int dx = p2.x - p1.x; const int dy = p2.y - p1.y; // horizontal line if (dy == 0) return static_cast<long>(p1.y) << 32 | 0; // vertical line if (dx == 0) return static_cast<long>(0)<< 32 | p1.x; const int d = __gcd(dx, dy); return static_cast<long>(dy / d) << 32 | (dx / d); } }; |