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