- 這一題的兩個關鍵點是
- 轉成角度,使用
atan2(dy, dx)
這個函式,並將 rad 轉成 degree。 - 要考慮座標 0 == 360,頭尾要相接。我的做法是將負數 +360 重覆放一遍。(或是只需要放小於 -180 + angle)
- 剩下的就是 sliding window 了。
class Solution {
public:
int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
vector<double> angles;
int on = 0;
for (const auto& p : points) {
int dy = p[1] - location[1];
int dx = p[0] - location[0];
if (dx == 0 && dy == 0) {
on++;
continue;
}
double ang = atan2(dy, dx) * 180 / std::numbers::pi;
if (ang < 180 + angle) angles.push_back(ang + 360);
angles.push_back(ang);
}
sort(angles.begin(), angles.end());
int left = 0, right = 0, res = 0, n = angles.size();
while (right < n) {
double curr = angles[right++];
while (curr - angles[left] > angle) left++;
res = max(res, right - left);
}
return res + on;
}
};