圆形靶内的最大飞镖数量

难度:

标签:

题目描述

Alice is throwing n darts on a very large wall. You are given an array darts where darts[i] = [x_i, y_i] is the position of the i^th dart that Alice threw on the wall.

Bob knows the positions of the n darts on the wall. He wants to place a dartboard of radius r on the wall so that the maximum number of darts that Alice throws lie on the dartboard.

Given the integer r, return the maximum number of darts that can lie on the dartboard.

Example 1:

Input: darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

Input: darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Constraints:

1 <= darts.length <= 100
darts[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
All the darts are unique
1 <= r <= 5000

代码结果

运行时间: 109 ms, 内存: 17.6 MB

/*
 * 思路：
 * 1. 枚举每两个飞镖位置的组合，计算它们的几何中点作为圆心
 * 2. 计算该几何中点距离两点的距离，确保它在半径范围内
 * 3. 使用此圆心和半径计算在圆内的飞镖数量
 * 4. 返回最大数量
 */

import java.util.*;
import java.util.stream.*;

public class DartboardStream {
    public int numPoints(int[][] darts, int r) {
        int n = darts.length;
        return IntStream.range(0, n).boxed()
                .flatMap(i -> IntStream.range(i + 1, n)
                        .mapToObj(j -> new int[][]{darts[i], darts[j]}))
                .filter(pair -> Math.hypot(pair[0][0] - pair[1][0], pair[0][1] - pair[1][1]) <= 2 * r)
                .flatMapToInt(pair -> IntStream.of(0, 1).map(k -> {
                    double midX = (pair[0][0] + pair[1][0]) / 2.0;
                    double midY = (pair[0][1] + pair[1][1]) / 2.0;
                    double angle = Math.atan2(pair[1][1] - pair[0][1], pair[1][0] - pair[0][0]);
                    double offset = Math.sqrt(r * r - (Math.hypot(pair[0][0] - pair[1][0], pair[0][1] - pair[1][1]) / 2) * (Math.hypot(pair[0][0] - pair[1][0], pair[0][1] - pair[1][1]) / 2));
                    double centerX = midX + offset * Math.cos(angle + (k == 0 ? Math.PI / 2 : -Math.PI / 2));
                    double centerY = midY + offset * Math.sin(angle + (k == 0 ? Math.PI / 2 : -Math.PI / 2));
                    return (int) Arrays.stream(darts)
                            .filter(dart -> Math.hypot(dart[0] - centerX, dart[1] - centerY) <= r)
                            .count();
                }))
                .max()
                .orElse(1); // 至少一个飞镖在圆内
    }

    public static void main(String[] args) {
        DartboardStream db = new DartboardStream();
        int[][] darts = {{-2, 0}, {2, 0}, {0, 2}, {0, -2}};
        int r = 2;
        System.out.println(db.numPoints(darts, r)); // 输出4
    }
}

解释

方法:

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

时间复杂度:

O(n^3 log n)

空间复杂度:

O(n^2)

代码细节讲解

🦆

在计算两点之间的距离时，为什么要加上一个非常小的值`1e-8`？这对结果有什么影响？

▷

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

🦆

为什么在处理角度事件时，需要将退出圆的事件设为负（`False`）？这样的设置有什么特定的理由或优势吗？

▷

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

🦆

您提到的角度排序中使用了`lambda x: [x[0], -x[1]]`，这里为什么要对第二个元素使用负号进行排序？

▷

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

圆形靶内的最大飞镖数量

题目描述

代码结果

解释

代码细节讲解

相关问题