)
LeetCode 1453 圆形靶内最大飞镖数量 题解
这道题的核心是：给定平面上的飞镖坐标和圆的半径，求最多有多少个飞镖能落在同一个半径为 r 的圆内（包括边界）。
解题思路
- 特殊情况：如果只有 1 个飞镖，答案直接是 1。
- 核心原理：两个点确定一个圆（半径固定为 r）。对于任意两个飞镖点，计算能同时包含这两个点的圆的圆心，再统计这个圆能覆盖多少个其他飞镖。
- 遍历所有点对：枚举所有两点组合，计算对应圆心，统计覆盖点数，最终取最大值。
- 精度处理：浮点数计算存在误差，判断点在圆内时用
距离平方 ≤ r² + 1e-8避免精度问题。
完整代码（Java）
importjava.util.*;publicclassSolution{publicintnumPoints(int[][]darts,intr){intn=darts.length;// 只有一个点，直接返回1if(n==1)return1;intmax=1;// 最少能覆盖1个点doublerSq=(double)r*r;// 半径平方，避免重复计算doubleeps=1e-8;// 精度误差值// 枚举所有两点组合for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){int[]p1=darts[i];int[]p2=darts[j];doublex1=p1[0],y1=p1[1];doublex2=p2[0],y2=p2[1];// 计算两点之间距离的平方doubledSq=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);// 两点距离超过直径2r，无法被同一个圆包含，跳过if(dSq>4*rSq+eps)continue;// 计算两个可能的圆心doublemidX=(x1+x2)/2.0;doublemidY=(y1+y2)/2.0;doubled=Math.sqrt(dSq);doubleh=Math.sqrt(rSq-dSq/4.0);// 圆心到两点连线的垂直距离// 第一个圆心doublecx1=midX+(y1-y2)*h/d;doublecy1=midY+(x2-x1)*h/d
