【排序】【二分】【角度制】个人练习-Leetcode-1610. Maximum Number of Visible Points

题目链接：https://leetcode.cn/problems/maximum-number-of-visible-points/

题目大意：给出一系列XY平面坐标点，给出你所在的坐标location，给出你的视角大小（角度制）angle。你可以在你的位置旋转任意角度来改变视角的范围，求能看到的最多点点数目。如果某个点和坐标重叠，那么视为可以看见并且它不会阻挡你看其他的点。

思路：将所有的点转为以location为原点的极坐标角度。如果某个点坐标和location相同，那么直接让结果+1，而不计算其角度。计算角度用到atan2()函数，它的值域范围是$[-\pi ,\pi ]$，可以覆盖到四个象限。

求能被框在angle范围内的角度的最大数目。排序后遍历即可。

但有注意点是：假设我们认为角度的范围为[-180, 180]，但有可能出现某个角度加上angle后超出这个范围，那么我们将所有角度加上360后排进原来的数列后面即可。

然而单纯的遍历会超时，鉴于角度数组是已经排过序的，需要用二分查找找第一个比x+angle大的角度的下标来将复杂度从O(N2)O(N^2)O(N2)降低到$O(NlogN)$

完整代码

class Solution {
public:int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {int ret = 0;vector<double> pa;for (auto p : points) {int dx = p[0] - location[0], dy = p[1] - location[1];if (dx == 0 && dy == 0)ret++;elsepa.emplace_back(atan2(dy, dx)/ M_PI * 180);}sort(pa.begin(), pa.end());int N = pa.size();vector<double> cp = pa;for (int i = 0; i < N; i++)pa.emplace_back(cp[i] + 360.0);int maxl = 0;for (int i = 0; i < N; i++) {double right = pa[i] + angle;auto pos = upper_bound(pa.begin()+i, pa.end(), right);int len = pos - pa.begin() - i;maxl = max(len, maxl);}ret += maxl;return ret;}
};