题目

类型：几何

解题思路

我们只需要算出每个坐标相对于 location 与 x 轴的夹角，然后，找到以每个坐标为起点，放置 angle 角度，这么大的辐射范围内的点数的最大值即可

假设，我们有上图所示的坐标系，里面有一些点，人所在的位置如图中小人标识位置，假设给定的辐射范围 angle 为 90°，那么，我们的计算过程如下：

• 先算出每个点与人位置坐标与 x 轴的夹角；
• 把这些点扔到 list 里面，并排序；
• 为了处理 180° 到 -180° 的过度，我们可以把所有的坐标加上 360° 再加一遍到 list 中。
• 遍历每一个坐标夹角 x，统计[x, x+angle]范围内的点数，这个过程我们可以使用滑动窗口或者二分查找实现，最后返回最大的点数即可。
• 注意，题目约定了你所在的位置也可能存在点，这些点需要特殊处理。

另外，本题我们可以使用库函数 atan2直接计算出夹角对应的弧度值，atan2 的返回值为[-π, π]

代码

class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        // 算出每一个坐标相对于location位置与x轴的夹角（弧度制），扔到List中排序
        // 然后对于每一个点，使用二分或滑动窗口找出小于这个点+angle（转成弧度制）的最大坐标点
        // 两者之间的下标差就是从这个点出发，辐射angle角度的点数量
        // 注意，与location点相同的点的特殊处理
        int same = 0;
        List<Double> list = new ArrayList<>();
        int x = location.get(0), y = location.get(1);
        for (List<Integer> point : points) {
            int a = point.get(0), b = point.get(1);
            if (a == x && b == y) {
                // 与location同点
                same++;
            } else {
                // 计算角度（弧度制）
                list.add(Math.atan2(b - y, a - x));
            }
        }
        // 排序
        Collections.sort(list);
        // 把前面所有的数添加一遍到后面，类似于于循环数组的使用
        int size = list.size();
        for (int i = 0; i < size; i++) {
            // 加 360度，然后范围相当于变成了 [-pi, 3*pi]
            list.add(list.get(i) + 2 * Math.PI);
        }
        double angleDegree = angle * Math.PI / 180;
        int max = 0;
        int i = 0, j = 0;
        while (i < size) {
            // 滑动窗口，简单点，list是有序的，使用二分查找也是可以的
            while (j < 2 * size && list.get(j) - list.get(i) <= angleDegree) {
                j++;
            }
            max = Math.max(max, j - i);
            i++;
        }
        return max + same;
    }
}