Hard

题目描述

Alice 向一面很大的墙投掷了 n 支飞镖。给你一个数组 darts，其中 darts[i] = [xi, yi] 是 Alice 投掷的第 i 支飞镖在墙上的位置。

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

给定整数 r，返回能够落在飞镖靶上的飞镖的最大数量。

示例 1：

输入：darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
输出：4
解释：以 (0,0) 为圆心，半径为 2 的圆形飞镖靶可以覆盖所有的点。

示例 2：

输入：darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出：5
解释：以 (0,4) 为圆心，半径为 5 的圆形飞镖靶可以覆盖除了 (7,8) 之外的所有点。

限制条件：

  • 1 <= darts.length <= 100
  • darts[i].length == 2
  • -10^4 <= xi, yi <= 10^4
  • 所有飞镖位置都是唯一的
  • 1 <= r <= 5000

解题思路

这道题需要找到一个半径为 r 的圆，使其能覆盖尽可能多的点。

核心观察： 如果存在最优解，我们总能移动圆，使得至少有两个点位于圆的边界上。这是因为如果圆内部有空隙，我们可以移动圆来包含更多点。

解题思路：

  1. 枚举所有点对： 对于任意两个点，最多可以确定两个半径为 r 的圆（这两个圆都经过这两个点）。

  2. 计算圆心： 给定两个点和半径 r，使用几何公式计算可能的圆心坐标。设两点为 A(x1,y1) 和 B(x2,y2)，首先计算两点中点和距离，然后利用垂直平分线求出圆心。

  3. 特殊情况处理：

    • 如果两点距离大于 2r，则无法找到经过两点的半径为 r 的圆
    • 如果两点重合，需要特别处理

  4. 统计覆盖点数： 对每个可能的圆心，统计有多少个点在以该点为圆心、半径为 r 的圆内（包括边界）。

  5. 优化： 还需要考虑只有一个点在圆边界上的情况，这时我们枚举每个点作为圆心的情况。

算法复杂度为 O(n³)，其中 n 是飞镖数量。由于 n ≤ 100，这个复杂度是可以接受的。

代码实现

class Solution {
public:
    int numPoints(vector<vector<int>>& darts, int r) {
        int n = darts.size();
        int maxPoints = 1;
        
        auto distance = [](double x1, double y1, double x2, double y2) {
            return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
        };
        
        auto countPointsInCircle = [&](double cx, double cy) {
            int count = 0;
            for (auto& dart : darts) {
                if (distance(cx, cy, dart[0], dart[1]) <= r + 1e-7) {
                    count++;
                }
            }
            return count;
        };
        
        // 枚举每一对点
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double x1 = darts[i][0], y1 = darts[i][1];
                double x2 = darts[j][0], y2 = darts[j][1];
                
                double d = distance(x1, y1, x2, y2);
                if (d > 2 * r) continue;
                
                // 计算两个可能的圆心
                double mx = (x1 + x2) / 2;
                double my = (y1 + y2) / 2;
                
                if (abs(d) < 1e-7) {
                    // 两点重合，以该点为圆心
                    maxPoints = max(maxPoints, countPointsInCircle(x1, y1));
                } else {
                    double h = sqrt(r * r - (d / 2) * (d / 2));
                    double ux = (y2 - y1) / d;
                    double uy = (x1 - x2) / d;
                    
                    double cx1 = mx + h * ux;
                    double cy1 = my + h * uy;
                    double cx2 = mx - h * ux;
                    double cy2 = my - h * uy;
                    
                    maxPoints = max(maxPoints, countPointsInCircle(cx1, cy1));
                    maxPoints = max(maxPoints, countPointsInCircle(cx2, cy2));
                }
            }
        }
        
        return maxPoints;
    }
};

class Solution:
    def numPoints(self, darts: List[List[int]], r: int) -> int:
        import math
        
        def distance(x1, y1, x2, y2):
            return math.sqrt((x1-x2)**2 + (y1-y2)**2)
        
        def count_points_in_circle(cx, cy):
            count = 0
            for dart in darts:
                if distance(cx, cy, dart[0], dart[1]) <= r + 1e-7:
                    count += 1
            return count
        
        n = len(darts)
        max_points = 1
        
        # 枚举每一对点
        for i in range(n):
            for j in range(i + 1, n):
                x1, y1 = darts[i]
                x2, y2 = darts[j]
                
                d = distance(x1, y1, x2, y2)
                if d > 2 * r:
                    continue
                
                # 计算两个可能的圆心
                mx = (x1 + x2) / 2
                my = (y1 + y2) / 2
                
                if abs(d) < 1e-7:
                    # 两点重合，以该点为圆心
                    max_points = max(max_points, count_points_in_circle(x1, y1))
                else:
                    h = math.sqrt(r * r - (d / 2) * (d / 2))
                    ux = (y2 - y1) / d
                    uy = (x1 - x2) / d
                    
                    cx1 = mx + h * ux
                    cy1 = my + h * uy
                    cx2 = mx - h * ux
                    cy2 = my - h * uy
                    
                    max_points = max(max_points, count_points_in_circle(cx1, cy1))
                    max_points = max(max_points, count_points_in_circle(cx2, cy2))
        
        return max_points

public class Solution {
    public int NumPoints(int[][] darts, int r) {
        int n = darts.Length;
        int maxPoints = 1;
        
        double Distance(double x1, double y1, double x2, double y2) {
            return Math.Sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
        }
        
        int CountPointsInCircle(double cx, double cy) {
            int count = 0;
            foreach (var dart in darts) {
                if (Distance(cx, cy, dart[0], dart[1]) <= r + 1e-7) {
                    count++;
                }
            }
            return count;
        }
        
        // 枚举每一对点
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double x1 = darts[i][0], y1 = darts[i][1];
                double x2 = darts[j][0], y2 = darts[j][1];
                
                double d = Distance(x1, y1, x2, y2);
                if (d > 2 * r) continue;
                
                // 计算两个可能的圆心
                double mx = (x1 + x2) / 2;
                double my = (y1 + y2) / 2;
                
                if (Math.Abs(d) < 1e-7) {
                    // 两点重合，以该点为圆心
                    maxPoints = Math.Max(maxPoints, CountPointsInCircle(x1, y1));
                } else {
                    double h = Math.Sqrt(r * r - (d / 2) * (d / 2));
                    double ux = (y2 - y1) / d;
                    double uy = (x1 - x2) / d;
                    
                    double cx1 = mx + h * ux;
                    double cy1 = my + h * uy;
                    double cx2 = mx - h * ux;
                    double cy2 = my - h * uy;
                    
                    maxPoints = Math.Max(maxPoints, CountPointsInCircle(cx1, cy1));
                    maxPoints = Math.Max(maxPoints, CountPointsInCircle(cx2, cy2));
                }
            }
        }
        
        return maxPoints;
    }
}

var numPoints = function(darts, r) {
    const n = darts.length;
    let maxPoints = 1;
    
    const distance = (x1, y1, x2, y2) => {
        return Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    };
    
    const countPointsInCircle = (cx, cy) => {
        let count = 0;
        for (const dart of darts) {
            if (distance(cx, cy, dart[0], dart[1]) <= r + 1e-7) {
                count++;
            }
        }
        return count;
    };
    
    // 枚举每一对点
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const x1 = darts[i][0], y1 = darts[i][1];
            const x2 = darts[j][0], y2 = darts[j][1];
            
            const d = distance(x1, y1, x2, y2);
            if (d > 2 * r) continue;
            
            // 计算两个可能的圆心
            const mx = (x1 + x2) / 2;
            const my = (y1 + y2) / 2;
            
            if (Math.abs(d) < 1e-7) {
                // 两点重合，以该点为圆心
                maxPoints = Math.max(maxPoints, countPointsInCircle(x1, y1));
            } else {
                const h = Math.sqrt(r * r - (d / 2) * (d / 2));
                const ux = (y2 - y1) / d;
                const uy = (x1 - x2) / d;
                
                const cx1 = mx + h * ux;
                const cy1 = my + h * uy;
                const cx2 = mx - h * ux;
                const cy2 = my - h * uy;
                
                maxPoints = Math.max(maxPoints, countPointsInCircle(cx1, cy1));
                maxPoints = Math.max(maxPoints, countPointsInCircle(cx2, cy2));
            }
        }
    }
    
    return maxPoints;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n³)枚举所有点对需要 O(n²)，对每个圆心统计覆盖点数需要 O(n)
空间复杂度O(1)只使用常数额外空间