记录编号	234985	评测结果	AAAAAAAAAA
题目名称	[SDOI 2012]拯救小云公主	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	2.445 s
提交时间	2016-03-10 07:52:26	内存使用	69.49 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int SIZEN=3010;
double zero=1e-5;
int N;
double row,line;
class miku
{
	public:
	double x,y;
}P[SIZEN];
void read()
{
	scanf("%d%lf%lf",&N,&row,&line);
	for(int i=1;i<=N;i++) scanf("%lf%lf",&P[i].x,&P[i].y);
}
double dis(int i,int j)
{
	return sqrt((P[j].x-P[i].x)*(P[j].x-P[i].x)+(P[j].y-P[i].y)*(P[j].y-P[i].y));
}
double dist[SIZEN][SIZEN];
int f[SIZEN];
int findb(int x)
{
	if(x==f[x]) return x;
	return f[x]=findb(f[x]);
}
void link(int x,int y)
{
	x=findb(x),y=findb(y);
	f[x]=y;
}
bool judge(double x)
{
	for(int i=0;i<=N+1;i++) f[i]=i;
	for(int i=1;i<=N;i++)
	{
		if(P[i].x-1.0<x||line-P[i].y<x) link(0,i);
		if(row-P[i].x<x||P[i].y-1.0<x) link(N+1,i);
		for(int j=i+1;j<=N;j++) 
		{
			if(dist[i][j]<2*x) link(i,j);
		}
	}
	int temx=findb(0),temy=findb(N+1);
	if(temx==temy) return 1;
	return 0;
}
void work()
{
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) dist[i][j]=dis(i,j);
	//for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) cout<<dist[i][j]<<" ";
	double l=0,r=row+line;
	while(r-l>zero)
	{
		double mid=(l+r)/2.0;
		if(judge(mid)) r=mid;
		else l=mid;
	}
	printf("%.2lf\n",l);
}
int main()
{
	freopen("dis.in","r",stdin);
	freopen("dis.out","w",stdout);
	read();
	work();
	return 0;
}