[数据结构与算法]Leetcode 1610 可见点的最大数目

题目

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

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

解题思路

??先对在观测点的被观测点计数 samePoints 。再对所有点计算其与观测点的弧度，这里用的 atan2 函数，其值域为 [-PI, PI] ，把值域转换成 [0, 2 * PI] ，将弧度转换成角度，则值域变成 [0°, 360°]，对所有角度排序，维护一个滑动窗口进行查找，直到找完整个数组。

??这么写会挂在第89组样例。对计算出来的角度，因为我是从第一象限开始遍历，到第四象限结束，那么就没有考虑到第一象限和第四象限结合的情况，所以还需要增加一整组角度，即将每个角度+360°加入数组中。

??麻了，这水题刚了半天。

class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        int length = points.size(), x0 = location.get(0), y0 = location.get(1), ans = 0, samePints = 0;
        List<Double> allAngles = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            int subX = points.get(i).get(0) - x0, subY = points.get(i).get(1) - y0;
            if (subX == 0 && subY == 0) {
                samePints++;
                continue;
            }
            double tmpAngle = Math.atan2(subY, subX) * (180 / Math.PI);
            if (tmpAngle < 0) tmpAngle += 360;
            allAngles.add(tmpAngle);
        }
        Collections.sort(allAngles);

        int n = allAngles.size();
        for (int i = 0; i < n; i++) {
            allAngles.add(allAngles.get(i) + 360);
        }

        int left = 0, right = 0;
        while (right < 2 * n) {
            if (allAngles.get(right) - allAngles.get(left) <= angle) {
                ans = Math.max(ans, right - left + 1);
                right++;
            } else {
                left++;
            }
        }
        return ans + samePints;
    }
}