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

#define MAXN 3010

#include<cmath>
#include<cstdio>

using namespace std;

int n,m,boss;
const double eps=1e-5;
int father[MAXN],f1,f2;
double L,R,mid,dis[MAXN][MAXN],Ans;
int up,left,right,low,first[MAXN],s;

struct Point{
	double x,y;
}pos[MAXN];

inline double Dis(Point a,Point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

inline int getf(int x)
{
	if(father[x]==x)return x;
	father[x]=getf(father[x]);
	return father[x];
}

inline bool Check()
{
	for(int i=1;i<=boss+4;i++)
	    father[i]=i;
	for(int i=1;i<=boss;i++)
	    for(int j=i+1;j<=boss;j++)
	        if(dis[i][j]<mid*2.0-eps){
				f1=getf(i+4);f2=getf(j+4);
				if(f1!=f2)father[f1]=f2;
	        }
	for(int i=1;i<=boss;i++){
		if(pos[i].y-1.00<mid-eps){
			f1=getf(low);f2=getf(i+4);
			if(f1!=f2)father[f1]=f2;
		}
		if(pos[i].x-1.00<mid-eps){
			f1=getf(left);f2=getf(i+4);
			if(f1!=f2)father[f1]=f2;
		}
		if((double)(m)-pos[i].y<mid-eps){
			f1=getf(up);f2=getf(i+4);
			if(f1!=f2)father[f1]=f2;
		}
		if((double)(n)-pos[i].x<mid-eps){
			f1=getf(right);f2=getf(i+4);
			if(f1!=f2)father[f1]=f2;
		}
	}
	if(getf(up)==getf(low))return false;
	if(getf(left)==getf(low))return false;
	if(getf(up)==getf(right))return false;
	if(getf(left)==getf(right))return false;
	return true;
}

int main()
{
    freopen("dis.in","r",stdin);
	freopen("dis.out","w",stdout);
	scanf("%d%d%d",&boss,&n,&m);
	for(int i=1;i<=boss;i++)
	    scanf("%lf%lf",&pos[i].x,&pos[i].y);
	for(int i=1;i<=boss;i++){
		dis[i][i]=0;
	    for(int j=i+1;j<=boss;j++)
	        dis[i][j]=dis[j][i]=Dis(pos[i],pos[j]);
	}
	up=1;low=2;left=3;right=4;
	L=0;R=1e3;Ans=0;
	while(R-L>eps){
		mid=(L+R)/2;
		if(Check())Ans=mid,L=mid;
		else R=mid;
	}
	printf("%0.2lf",Ans);
}