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

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double dl;
typedef long long ll;
class poi{
public:
	int x,y;
}s[3001];
int n,row,line;
dl ans=0.0;
int p[30002];
dl l,r,mid;
void work();
int find(int x);
bool tmp(dl k);
dl d(int l,int r);
int main(){
	freopen("dis.in","r",stdin);
	freopen("dis.out","w",stdout);
	scanf("%d%d%d",&n,&row,&line);
	for (int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);
	work();
	printf("%.2lf",ans);
	return 0;
}
void work(){
	l=0;
	r=(dl)max(row,line);
	while(l+0.0001<r){
		//printf("%.2lf %.2lf\n",l,r);
		mid=(dl)(l+r)/2;
		if (tmp((dl)mid)==1) r=mid;
		else l=mid;
	}
	ans=(dl)l;
	return;
}
int find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
dl d(int l,int r){
	dl a=s[l].x-s[r].x;
	dl b=s[l].y-s[r].y;
	return sqrt(a*a+b*b);
}
bool tmp(dl k){
	for (int i=0;i<=n+1;i++) p[i]=i;
	int a=0,b=0;
	for (int i=1;i<=n;i++){
		if (s[i].x-1<k||line-s[i].y<k) {
			a=find(i);
			p[a]=find(0);
		}
		if (row-s[i].x<k||s[i].y-1<k){
			a=find(i);
			p[a]=find(n+1);
		}
		for (int j=i+1;j<=n;j++) if (d(i,j)<2*k){
			a=find(i);
			b=find(j);
			p[b]=a;
		}
		if (find(0)==find(n+1)) return 1;
	}
	return 0;
}