Description
给定\(n\)个整数点的二维坐标\((x_i, y_i)\)，求最多的连在同一直线上的点数目。
Constraints
- \(1 \le n \le 300\)
- \(-10^4 \le x_i, y_i \le 10^4\)
- 不存在重复的点
Solution
计算几何就从来没做过，还好这题思路简单。
哈希表配合gcd记录斜率即可。需要注意的是横竖两种情况要特殊维护。
Code
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
auto gcd = [](auto &&gcd, int a, int b) -> int {
return b ? gcd(gcd, b, a%b) : a;
};
auto h = [](auto &&tup) {
auto &&[x, y] = tup;
auto make_hash = []<typename T>(T &&v) {
return hash<decay_t<T>>{}(v);
};
return make_hash(x) ^ make_hash(y);
};
using Map = unordered_map<tuple<int, int>, int, decltype(h)>;
int ans {};
for(size_t i = 0; i < points.size(); ++i) {
// special cases
int sc1 {}, sc2 {};
Map rec(0, h);
for(size_t j = 0; j < i; ++j) {
auto p1 = points[i], p2 = points[j];
auto [x1, y1] = make_tuple(p1[0], p1[1]);
auto [x2, y2] = make_tuple(p2[0], p2[1]);
auto dx = x1 - x2, dy = y1 - y2;
if(!dx || !dy) {
++(dx ? sc1 : sc2);
continue;
}
bool neg = 0;
if(dx < 0) neg ^= 1, dx = -dx;
if(dy < 0) neg ^= 1, dy = -dy;
int g = gcd(gcd, dx, dy);
dx /= g; dy /= g;
if(neg) dx = -dx;
rec[make_tuple(dx, dy)]++;
}
for(auto [_, v] : rec) ans = max(ans, v);
ans = max({ans, sc1, sc2});
}
return ans + 1;
}
};