比赛 |
20160309 |
评测结果 |
AAAAAAAAAA |
题目名称 |
拯救小云公主 |
最终得分 |
100 |
用户昵称 |
zys |
运行时间 |
1.217 s |
代码语言 |
C++ |
内存使用 |
69.48 MiB |
提交时间 |
2016-03-09 21:44:16 |
显示代码纯文本
#define MAXN 3010
#include<cmath>
#include<cstdio>
using namespace std;
int n,m,boss;
const double eps=1e-5;
int father[MAXN],f1,f2;
double L,R,mid,dis[MAXN][MAXN],Ans;
int up,left,right,low,first[MAXN],s;
struct Point{
double x,y;
}pos[MAXN];
inline double Dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline int getf(int x)
{
if(father[x]==x)return x;
father[x]=getf(father[x]);
return father[x];
}
inline bool Check()
{
for(int i=1;i<=boss+4;i++)
father[i]=i;
for(int i=1;i<=boss;i++)
for(int j=i+1;j<=boss;j++)
if(dis[i][j]<mid*2.0-eps){
f1=getf(i+4);f2=getf(j+4);
if(f1!=f2)father[f1]=f2;
}
for(int i=1;i<=boss;i++){
if(pos[i].y-1.00<mid-eps){
f1=getf(low);f2=getf(i+4);
if(f1!=f2)father[f1]=f2;
}
if(pos[i].x-1.00<mid-eps){
f1=getf(left);f2=getf(i+4);
if(f1!=f2)father[f1]=f2;
}
if((double)(m)-pos[i].y<mid-eps){
f1=getf(up);f2=getf(i+4);
if(f1!=f2)father[f1]=f2;
}
if((double)(n)-pos[i].x<mid-eps){
f1=getf(right);f2=getf(i+4);
if(f1!=f2)father[f1]=f2;
}
}
if(getf(up)==getf(low))return false;
if(getf(left)==getf(low))return false;
if(getf(up)==getf(right))return false;
if(getf(left)==getf(right))return false;
return true;
}
int main()
{
freopen("dis.in","r",stdin);
freopen("dis.out","w",stdout);
scanf("%d%d%d",&boss,&n,&m);
for(int i=1;i<=boss;i++)
scanf("%lf%lf",&pos[i].x,&pos[i].y);
for(int i=1;i<=boss;i++){
dis[i][i]=0;
for(int j=i+1;j<=boss;j++)
dis[i][j]=dis[j][i]=Dis(pos[i],pos[j]);
}
up=1;low=2;left=3;right=4;
L=0;R=1e3;Ans=0;
while(R-L>eps){
mid=(L+R)/2;
if(Check())Ans=mid,L=mid;
else R=mid;
}
printf("%0.2lf",Ans);
}