圆形靶内的最大飞镖数量

标签: 几何 数组 数学

难度: Hard

Alice 向一面非常大的墙上掷出 n 支飞镖。给你一个数组 darts ，其中 darts[i] = [xi, yi] 表示 Alice 掷出的第 i 支飞镖落在墙上的位置。

Bob 知道墙上所有 n 支飞镖的位置。他想要往墙上放置一个半径为 r 的圆形靶。使 Alice 掷出的飞镖尽可能多地落在靶上。

给你整数 r ，请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。

示例 1 ：

输入：darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
输出：4
解释：如果圆形靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。

示例 2 ：

输入：darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出：5
解释：如果圆形靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。

提示：

  • 1 <= darts.length <= 100
  • darts[i].length == 2
  • -104 <= xi, yi <= 104
  • darts 中的元素互不相同
  • 1 <= r <= 5000

Submission

运行时间: 109 ms

内存: 17.6 MB

class Solution:
    def numPoints(self, points: List[List[int]], r: int) -> int:
        def helper(i, r, n):
            angles = []
            for j in range(n):
                if i != j and (l2 := sum([_ ** 2 for _ in vec[i][j]])) <= (2 * r) ** 2 + 1e-8:
                    C = math.acos(math.sqrt(l2) / (2 * r))
                    T = math.atan2(vec[i][j][1], vec[i][j][0])
                    _in = T - C
                    _out = T + C
                    angles.append([_in, True])
                    angles.append([_out, False])
            # 这里排序是重点, 考虑边界条件
            # 比如有 [0, False], [0, True]
            # 要让[0, True] 排到 [0, False]前面
            angles.sort(key=lambda x: [x[0], - x[1]])
            cnt = res = 1
            for item in angles:
                if item[1]:
                    cnt += 1
                else:
                    cnt -= 1
                if cnt > res:
                    res = cnt
            return res

        n = len(points)
        if n == 1:
            return 1
        # vec[i][j] = [Jx - Ix, J_y - Iy]
        # vec 存入两点之间的方向向量
        vec = [[[0, 0] for _ in range(n)] for __ in range(n)]
        for i in range(n - 1):
            for j in range(i + 1, n):
                JxIx = points[j][0] - points[i][0]
                JyIy = points[j][1] - points[i][1]
                vec[i][j] = [JxIx, JyIy]
                vec[j][i] = [-JxIx, -JyIy]
        ans = 0
        for i in range(n):
            ans = max(ans, helper(i, r, n))

        return ans

# 作者：lih627
# 链接：https://leetcode.cn/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/solutions/250547/python3-angular-sweepsuan-fa-by-lih/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Explain

这道题的解决方案使用了角度扫描的方法。首先，对于每个点，计算它与其他所有点之间的角度，如果两点之间的距离小于等于直径，则这两点可以由同一个圆覆盖。基于这两点之间的中点和向量方向，我们可以计算出两个角度——入圈和出圈的角度。将这些角度事件存储起来，并进行排序。排序后，通过遍历这些角度事件，并用一个计数器来追踪当前圆内飞镖的数量，就可以找到最多的飞镖数量。通过比较所有点作为圆心时的最大值，得到最终答案。

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

空间复杂度: O(n^2)

class Solution:
    def numPoints(self, points: List[List[int]], r: int) -> int:
        def helper(i, r, n):
            angles = []
            for j in range(n):
                if i != j and (l2 := sum([_ ** 2 for _ in vec[i][j]])) <= (2 * r) ** 2 + 1e-8:
                    C = math.acos(math.sqrt(l2) / (2 * r))
                    T = math.atan2(vec[i][j][1], vec[i][j][0])
                    _in = T - C
                    _out = T + C
                    angles.append([_in, True])
                    angles.append([_out, False])
            angles.sort(key=lambda x: [x[0], -x[1]])
            cnt = res = 1
            for item in angles:
                if item[1]:
                    cnt += 1
                else:
                    cnt -= 1
                if cnt > res:
                    res = cnt
            return res
        n = len(points)
        if n == 1:
            return 1
        vec = [[[0, 0] for _ in range(n)] for __ in range(n)]
        for i in range(n - 1):
            for j in range(i + 1, n):
                JxIx = points[j][0] - points[i][0]
                JyIy = points[j][1] - points[i][1]
                vec[i][j] = [JxIx, JyIy]
                vec[j][i] = [-JxIx, -JyIy]
        ans = 0
        for i in range(n):
            ans = max(ans, helper(i, r, n))
        return ans
# 在这里提供了每个重要代码段的注释，描述了它的作用。

Explore

在计算两点之间的距离时加上一个非常小的值`1e-8`，主要是为了处理浮点数运算中的精度问题。由于计算机中浮点数的存储和计算通常会有精度误差，当两点之间的距离非常接近圆的直径时，直接的计算可能导致一些本应在圆内的点被错误地判定为在圆外。通过加上一个微小的值，可以确保这种边界情况下，计算更加偏向于将点包含在圆内，从而避免由于浮点误差导致的错误判定。

在处理角度事件时，将退出圆的事件设为负（`False`）主要是为了方便在遍历这些事件时管理圆内飞镖的数量。每当遇到一个入圈事件（`True`），计数器增加，表示新的飞镖进入了圆内；每当遇到一个出圈事件（`False`），计数器减少，表示有飞镖离开了圆内。这种设置使得算法可以简单地通过增加和减少计数器的值来更新当前圆内的飞镖数量，从而快速地计算出任何时间点圆内包含的最大飞镖数。

在角度排序中使用`lambda x: [x[0], -x[1]]`对第二个元素使用负号进行排序的主要原因是确保在相同的角度上，入圈事件（`True`）优先于出圈事件（`False`）处理。这是因为在实际场景中，一个飞镖恰好在某一个角度同时入圈和出圈，我们希望首先考虑它进入圈内（增加计数），然后再考虑它离开（减少计数）。这样的排序确保了计数器逻辑的正确性，允许我们准确地计算出任何时刻圆内的飞镖数量。