题意分析

题目要求：在给定的N个平面点中，找到一个半径为1的圆，使得该圆能够覆盖（包含在圆内或圆上）尽可能多的点。需要输出每个测试用例中能被单个单位圆覆盖的最大点数。

1.输入说明：

多组测试数据，每组数据包含：

整数$N（1 ≤ N ≤ 300）$，表示点的数量

接下来N行，每行两个浮点数(X,Y)表示点的坐标$（0.0 ≤ X,Y ≤ 10.0）$

输入以单独一行0结束

2.特殊条件保证：

任意两点距离不小于$0.0001$

不存在两点距离在$[1.9999, 2.0001]$范围内

不存在三个点同时接近某个单位圆的边界（与圆心的距离均在$[0.9999, 1.0001]）$

3.输出要求：

对每组数据，输出能被一个单位圆覆盖的最大点数。

解题思路

1.关键观察： 最优圆的位置特性：最大覆盖圆必定有至少两个给定点在其边界上（否则可以通过平移扩大覆盖）

圆心的确定：给定两点和半径，可以确定两个可能的圆心（题目保证不存在两点距离恰为2.0，故圆心唯一）

2.算法选择： 枚举所有点对： 对于每对距离≤2.0的点，计算它们确定的单位圆圆心 检查每个圆心能覆盖多少点

3.优化处理：

预处理所有点坐标

对每对点$(i,j)$，若距离>2.0则跳过（无法共圆）

计算圆心时利用几何性质简化运算

使用$\varepsilon = 10^{-8}$处理浮点精度问题

4.具体步骤：

输入点坐标

初始化$maxsum=1$（至少能覆盖一个点）

双重循环枚举所有点对(i,j)： a. 计算两点距离，若>2.0则跳过 b. 计算这两点确定的单位圆圆心 c. 遍历所有点，统计在圆内或圆上的点数 d. 更新maxsum

输出maxsum

代码实现

#include<cstring>
#include<iostream>
#include<cmath>
#include <cstdio> 
#define db double
using namespace std;
const db eps=1e-8;
struct Point{
	db x,y;
	Point(db x=0,db y=0):x(x),y(y){}
}p[305];
int n;
db Dist(Point p1,Point p2){
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
Point GetCenter(Point p1,Point p2){
	Point mid=Point((p1.x+p2.x)/2,(p1.y+p2.y)/2);
	db angle=atan2(p1.x-p2.x,p2.y-p1.y);
	db d=sqrt(1-Dist(p1,mid)*Dist(p1,mid));
	return Point(mid.x+d*cos(angle),mid.y+d*sin(angle));
}
int main(){
	while(scanf("%d",&n)==1){
		if(!n) break;
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		int maxsum=1;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				if(Dist(p[i],p[j])>2.0) continue;
				Point center=GetCenter(p[i],p[j]);
				int sum=0;
				for(int k=0;k<n;k++)
					if(Dist(center,p[k])<1.0+eps)
						sum++;
				maxsum=max(maxsum,sum);
			}
		}
		printf("%d\n",maxsum);
	}
	return 0;
}