传送门 LeeCode 1610. 可见点的最大数目
区间 [ d − a n g l e / 2 , d + a n g l e / 2 ] [d - angle/2, d + angle/2] [d−angle/2,d+angle/2] 左界代表的角度逆时针移动后，满足区间代表的角度差小于等于 a n g l e angle angle，那么可以使用尺取法求解大小为 a n g l e angle angle 的区间内的最大点数。
考虑到 x x x 正半轴左右侧极限相差 2 π 2\pi 2π，那么可以拆环成链，即，将观察者与点的相对于坐标轴的夹角加上 2 π 2\pi 2π 后加入数组，排序求解。要特殊考虑与观察者位于同一位置的点，预先统计。
class Solution { public: int visiblePoints(vector<vector<int>> &points, int angle, vector<int> &location) { int n = points.size(), x = location[0], y = location[1]; double pi = acos(-1), angle2 = angle / 180.0 * pi; vector<double> ang(n << 1); int i = 0, cnt = 0; for (auto p : points) { double dx = p[0] - x, dy = p[1] - y; bool f = 0; if (dx < 0) { f = 1; } if (dx == 0 && dy == 0) { ++cnt; continue; } double tmp = dx == 0 ? (dy > 0 ? pi / 2 : -pi / 2) : atan(dy / dx); if (f) { tmp += pi; } if (tmp < 0) { tmp += 2 * pi; } ang[i++] = tmp; } sort(ang.begin(), ang.begin() + i); for (int j = 0; j < i; j++) { ang[i + j] = ang[j] + 2 * pi; } int sz = i << 1; int l = 0, r = 0, res = 0; for (;;) { while (l < i && r < sz && r - l <= i && (ang[r] - ang[l]) <= angle2) { ++r; } res = max(res, r - l); if (l == i || r == sz || r - l == i) { break; } ++l; } return res + cnt; } };