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

#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define N 3030
using namespace std;
typedef double ld;
ifstream in("dis.in");
ofstream out("dis.out");
int n;
int f[N]={0},g[N]={0},X,Y;
ld o[N][N]={0};
class point
{
public:
	ld x,y;
	void make(ld a,ld b)
	{
		x=a;
		y=b;
	}
	void print()
	{
		out<<x<<' '<<y<<endl;
	}
}p[N];
void read()
{
	int i,j;
	in>>n>>X>>Y;
	for(i=1;i<=n;i++)in>>p[i].x>>p[i].y;
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			o[i][j]=o[j][i]=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
		}
	}
}
int find(int x)
{
	if(f[x]==x)return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y)
{
	x=find(x);y=find(y);
	if(g[x]>g[y])f[y]=x;
	else
	{
		f[x]=y;
		if(g[x]==g[y])g[y]++;
	}
}
bool check(ld R)
{
	int i,j;
	for(i=1;i<=n+2;i++)f[i]=i,g[i]=0;
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			if(o[i][j]<=2*R)merge(i,j);
		}
	}
	for(i=1;i<=n;i++)
	{
		if(p[i].x-R<=1||p[i].y+R>=Y)merge(i,n+1);
		if(p[i].x+R>=X||p[i].y-R<=1)merge(i,n+2);
	}
	if(find(n+1)==find(n+2))return 0;
	return 1;
}
void print(ld x,int y)
{
	out <<setprecision(y) <<std::fixed<<x<<endl;
}
void work()
{
	ld l,r,mid,eps=0.001;
	l=0;
	r=fmax(X,Y);
	while(r-l>=eps)
	{
		mid=(l+r)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	print(l,2);
}
int main()
{
	read();
	work();
	return 0;
}