题目描述

给你一个点数组 points 和一个表示角度的整数 angle，你的位置是 location，其中 location = [pos_x, pos_y] 且 points[i] = [x_i, y_i] 都表示 X-Y 平面上的整数坐标。

最开始，你面向东方进行观测。你 不能 进行移动改变位置，但可以通过 自转 调整观测角度。换句话说，pos_x 和 pos_y 不能改变。你的视野范围的角度用 angle 表示，这决定了你观测任意方向时可以多宽。设 d 为你逆时针自转旋转的度数，那么你的视野就是角度范围 [d - angle/2, d + angle/2] 所指示的那片区域。

对于每个点，如果由该点、你的位置以及从你的位置直接向东的方向形成的角度 位于你的视野中，那么你就可以看到它。

同一个坐标上可以有多个点。你所在的位置也可能存在一些点，但不管你的怎么旋转，总是可以看到这些点。同时，点不会阻碍你看到其他点。

返回你能看到的点的最大数目。

样例

输入：points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1]
输出：3
解释：阴影区域代表你的视野。在你的视野中，所有的点都清晰可见。
尽管 [2,2] 和 [3,3]在同一条直线上，你仍然可以看到 [3,3]。

输入：points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1]
输出：4
解释：在你的视野中，所有的点都清晰可见，包括你所在位置的那个点。

输入：points = [[1,0],[2,1]], angle = 13, location = [1,1]
输出：1
解释：如图所示，你只能看到两点之一。

限制

• 1 <= points.length <= 10^5
• points[i].length == 2
• location.length == 2
• 0 <= angle < 360
• 0 <= pos_x, pos_y, x_i, y_i <= 10^9

算法

(极坐标排序，计算几何，双指针) $O(n \log n)$

1. 首先将所有点的坐标减去 location 的坐标，统计出与 location 相同的点。
2. 然后用 atan2 求出每个不与 location 相同的点的正切值，记录到新的数组里，然后从小到大排序。注意正切值是弧度值，范围是 $[-\pi, \pi]$。
3. 由于这是个环形的问题，我们需要把数组的长度扩充一倍，且扩充的正切值要比原值大 $2\pi$。
4. 用双指针来求解最多能看到的点的个数，对于每个点 $i$，求出最小的 $j$，满足点 $i$ 和 $j$ 之间的夹角小于等于 angle。注意到 $j$ 是随着 $i$ 单调不降的。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 双指针的时间复杂度为线性，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储正切值。

C++ 代码

class Solution {
public:
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
        int original = 0;
        vector<double> angles;
        for (const auto &point : points) {
            if (point == location) {
                original++;
                continue;
            }
            angles.push_back(atan2(point[1] - location[1], point[0] - location[0]));
        }
        sort(angles.begin(), angles.end());

        const double PI = acos(-1);
        const int n = angles.size();
        int ans = 0;

        for (int i = 0; i < n; i++)
            angles.push_back(angles[i] + 2 * PI);

        for (int i = 0, j = 0; i < 2 * n; i++) {
            while (angles[i] - angles[j] > angle * PI / 180)
                j++;

            if (ans < i - j + 1)
                ans = i - j + 1;
        }

        return ans + original;
    }
};