比赛 |
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;
}