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