可见点的最大数目

标签: 几何 数组 数学 排序 滑动窗口

难度: Hard

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

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

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

  • 1 <= points.length <= 105
  • points[i].length == 2
  • location.length == 2
  • 0 <= angle < 360
  • 0 <= posx, posy, xi, yi <= 100

Submission

运行时间: 315 ms

内存: 43.2 MB

class Solution:
    def visiblePoints(
        self, points: List[List[int]], angle: int, location: List[int]
    ) -> int:
        v = []
        x, y = location
        same = 0
        for xi, yi in points:
            if xi == x and yi == y:
                same += 1
            else:
                v.append(atan2(yi - y, xi - x))
        v.sort()
        n = len(v)
        v += [deg + 2 * pi for deg in v]
        t = angle * pi / 180
        mx = max((bisect_right(v, v[i] + t) - i for i in range(n)), default=0)
        return mx + same

Explain

该题解首先计算所有点相对于观测位置的极角（通过atan2函数），并存储这些角度。如果点位于观测者的位置上，该点始终可见，记录这类点的数量。接下来，对角度进行排序，并通过复制一份角度列表并添加2*pi（将度数转换为弧度）到每个角度，以模拟一个360度的环。这样做是为了处理环绕效果，即视野跨越360度零界点的情况。使用二分搜索（bisect_right），找到每个角度加上视角（转换为弧度）后能看到的最远点，计算这个范围内包含的点的数量。最后，找出这些范围中包含点数最多的一个，并加上始终可见的点的数量。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        v = []  # 用于存储点的角度
        x, y = location  # 观测者的位置
        same = 0  # 在同一位置的点数
        for xi, yi in points:
            if xi == x and yi == y:
                same += 1  # 累加在同一位置的点
            else:
                v.append(atan2(yi - y, xi - x))  # 计算并存储每个点的角度
        v.sort()  # 排序角度
        n = len(v)  # 点的数量
        v += [deg + 2 * pi for deg in v]  # 复制并处理360度环绕
        t = angle * pi / 180  # 角度转为弧度
        # 使用二分查找找出每个角度视角内最多可见的点
        mx = max((bisect_right(v, v[i] + t) - i for i in range(n)), default=0)
        return mx + same  # 返回最大可见点数加上始终可见的点

Explore

使用atan2函数计算极角的主要优势在于它可以直接根据点的x和y坐标差值（相对于观测点）输出正确的角度值，范围从-pi到pi。这包括了所有四个象限的考虑，无需额外的条件判断。相对于简单的arctan或其他计算方法，atan2能自动处理x坐标为0的情况，且能正确区分角度的正负，这对于后续的角度比较和排序至关重要。

通过首先对角度列表进行排序，确保角度的顺序性。接着，通过复制整个角度列表并将每个角度增加2*pi（360度），添加到原列表后面，形成一个扩展的角度列表。这种方法模拟了一个360度的环，允许计算跨越360度零界点的视角。例如，如果一个角度接近360度，通过这种扩展，可以直接搜索到原始列表中靠近0度的角度，从而正确处理视角的环绕效应。

bisect_right函数用来在排序的列表中找到某个值应该插入的位置，而使列表仍保持排序。在此算法中，对于每一个角度v[i]，使用bisect_right来找到v[i]加上视角t后的角度（v[i] + t）应该插入的位置。这个位置即是在当前角度v[i]加上视角t之内能够观测到的最远点的索引。因此，这个索引减去i（当前角度的索引）就给出了在这个视角范围内可见点的数量。

该算法确实考虑了角度angle为0或非常小的情况。当angle为0时，视角范围非常小，理论上只能看到与观测点完全重合的点。在这种情况下，算法通过变量same来记录与观测点重合的点数。因此，即使angle为0，算法依然能正确返回与观测点重合的点的数量。对于非常小的angle值，相应的视角范围也非常小，可能只包含极少数或没有任何其他点，此时主要的输出依赖于same变量的值。