比赛 20160309 评测结果 AAAAAAAAAA
题目名称 拯救小云公主 最终得分 100
用户昵称 Fmuckss 运行时间 1.310 s
代码语言 C++ 内存使用 138.16 MiB
提交时间 2016-03-09 21:09:22
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm> 
using namespace std;
const int inf = 1e9;
const double ex = 1/1e3;
const int maxn = 3005;
const double two = 2;
bool vis[maxn];
double dis[maxn][maxn];
int n;
double x, y;
struct node {
	double x, y;
	double gdis(const node &b) const	{
		return sqrt((b.x-x)*(b.x-x) + (b.y-y)*(b.y-y));
	}
}ns[maxn];
int get_num() {
	int ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp >= '0' && tmp <= '9') {
		ans = ans*10 + tmp -'0';
		tmp = getchar();
	}
	return ans;
}
struct edge {
	int to, ne;
}e[maxn*maxn];
int head[maxn], tot;
void addedge(int a, int b) {
	++tot; e[tot].to = b; e[tot].ne = head[a]; head[a] = tot;
	++tot; e[tot].to = a; e[tot].ne = head[b]; head[b] = tot;
}
void beg() {
	for(int i = 1; i <= n+2; i++) {
		vis[i] = false;
		head[i] = 0;
	}
	tot = 0;
}
void get_dis() {
	for(int i = 1; i <= n; i++) {
		for(int j = i+1; j <= n; j++) {
			dis[i][j] = ns[i].gdis(ns[j]);
		}
	}
}
void make_graph(double num) {
	for(int i = 1; i <= n; i++) {
		if(ns[i].x-1 < num || y-ns[i].y < num) addedge(n+1, i);
		if(x-ns[i].x < num || ns[i].y-1 < num) addedge(n+2, i);
		for(int j = i+1; j <= n; j++) {
			if(dis[i][j] < 2*num) addedge(i, j);
		}
	}
}
bool judge(double num) {
	beg();
	make_graph(num);
	queue<int> q;
	q.push(n+1);
	int now;
	while(!q.empty()) {
		now = q.front();
		q.pop();
		int to;
		for(int i = head[now]; i; i = e[i].ne) {
			to = e[i].to;
			if(vis[to]) continue;
			vis[to] = true;
			q.push(to);
			if(to == n+2) return true;
		}
	}
	return false;
}
void read() {
	n = (double) get_num();
	x = (double) get_num();
	y = (double) get_num();
	for(int i = 1; i <= n; i++) {
		ns[i].x = (double) get_num();
		ns[i].y = (double) get_num();
	}
}
double solve() {
	get_dis();
	double l = 0, r = (double)max(x, y)+1, mid;
	while(l+ex < r) {
		mid = (l+r)/two;
		if(judge(mid)) r = mid;
		else l = mid;
	}
	return (l+r)/two;
}
int main() {
	freopen("dis.in","r",stdin);
	freopen("dis.out","w",stdout);
	read();
	printf("%.2lf", solve());
	return 0;
}