比赛 20160309 评测结果 AAAAAWWTAT
题目名称 拯救小云公主 最终得分 60
用户昵称 农场主 运行时间 3.698 s
代码语言 C++ 内存使用 0.38 MiB
提交时间 2016-03-09 21:55:23
显示代码纯文本
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstring>
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;
vector<int> v[3002];
bool t[3002]={0};
int p[3002];
long long l,r,mid;
void work();
int find(int x);
bool tmp(dl k);
dl abs(dl x);
dl d(int l,int r);
bool dfs(int x);
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=(ll)max(row,line)*100;
	while(l+1<r){
		mid=(ll)(l+r)/2;
		if (tmp((dl)mid/100)==1) r=mid;
		else l=mid;
	}
	ans=(dl)l/100;
	return;
}
int find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
dl abs(dl x){
	if (x<0) return -1*x;
	else return x;
}
dl d(int l,int r){
	dl a=abs(s[l].x-s[r].x);
	dl b=abs(s[l].y-s[r].y);
	return sqrt(a*a+b*b);
}
bool dfs(int x){
	if (t[x]==1) return 0;
	t[x]=1;
	int a=find(x);
	for (int i=0;i<v[x].size();i++){
		int b=find(v[x][i]);
		p[b]=p[a];
		if (dfs(v[x][i])==1) return 1;
	}
	if (find(0)==find(n+1)) return 1;
	return 0;
}
bool tmp(dl k){
	memset(t,0,sizeof(t));
	for (int i=0;i<=n+1;i++) { v[i].clear(); p[i]=i; }
	for (int i=1;i<=n;i++){
		if (s[i].x-1<k||line-s[i].y<k) {
			v[i].push_back(0);
			v[0].push_back(i);
		}
		if (row-s[i].x<k||s[i].y-1<k){
			v[i].push_back(n+1);
			v[n+1].push_back(i);
		}
		for (int j=i+1;j<=n;j++) if (d(i,j)<2*k){
			v[i].push_back(j);
			v[j].push_back(i);
		}
	}
	return dfs(0);
}