题解 P2498 【[SDOI2012]拯救小云公主】
顾z
2018-11-17 21:37:41
> ### Description
>
> 英雄又即将踏上拯救公主的道路……
>
> 这次的拯救目标是——爱和正义的小云公主。
>
> 英雄来到boss的洞穴门口，他一下子就懵了，因为面前不只是一只boss，而是上千只boss。当英雄意识到自己还是等级1的时候，他明白这就是一个不可能完成的任务。
>
> 但他不死心，他在想，能不能避开boss去拯救公主呢，嘻嘻。
>
> Boss的洞穴可以看成一个矩形，英雄在左下角（1,1），公主在右上角（row，line）。英雄为了避开boss，当然是离boss距离越远越好了，所以英雄决定找一条路径使到距离boss的最短距离最远。
>
> Ps:英雄走的方向是任意的。
>
> 你可以帮帮他吗？
>
> 当英雄找到了美丽漂亮的小云公主，立刻就被boss包围了！！！英雄缓闭双眼，举手轻挥，白光一闪后使用了回城卷轴，回到了城堡，但只有小云公主回去了……因为英雄忘了进入回城的法阵了。
>
> ### Input
>
> 第一行，输入三个整数，n表示boss的数目，row，line表示矩形的大小；
>
> 接下来n行，每行分别两个整数表示boss的位置坐标。
>
> ### Output
>
> 输出一个小数，表示英雄的路径离boss的最远距离，精确到小数点后两位。
这里的距离指的是**欧几里德距离**。
首先很容易看出是**二分答案**。
我们可以看成是以每个$boss$为圆心作一个半径为$r$的圆,我们想要求的就是让这些圆尽可能大,并且不能影响我们从$(1,1)$到$(n,m)$。(不能覆盖)
直接考虑边界条件$(n,1)$和$(1,m)$如果这两个点没有被覆盖,那我必然可以到达$(n,m)$
PS：这里的判断条件不是同时判断。
这样用$||$判断,可以达到我们边界不被封锁的情况。
用**并查集**维护连通即可。
``代码``
```c++
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define eps 1e-4
#define R register
using namespace std;
const int gz=3e3+8;
inline void in(R int &x)
{
R int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int nn,n,m,f[gz];
struct cod
{
int x,y;
}bos[gz];
int find(R int x){return f[x]==x?x:f[x]=find(f[x]);}
inline double xx(R double x)
{
return x*x;
}
inline double dis(R int i,R int j)
{
return xx(bos[i].x-bos[j].x)+xx(bos[i].y-bos[j].y);
}
inline bool ok(R double r)
{
for(R int i=0;i<=nn+1;i++)f[i]=i;
for(R int i=1;i<=nn;i++)
{
for(R int j=1;j<i;j++)
{
if(dis(i,j)<=xx(2*r))
{
R int fa=find(i),fb=find(j);
if(fa!=fb)f[fa]=fb;
}
}
if(bos[i].x-r<=1 or bos[i].y+r>=m)
{
R int fa=find(i),fb=find(0);
if(fa!=fb)f[fa]=fb;
}
if(bos[i].x+r>=n or bos[i].y-r<=1)
{
R int fa=find(i),fb=find(nn+1);
if(fa!=fb)f[fa]=fb;
}
}
return find(0)!=find(nn+1);
}
int main()
{
in(nn),in(n),in(m);
for(R int i=1;i<=nn;i++)
in(bos[i].x),in(bos[i].y);
R double ll=0,rr=min(n,m);
while(fabs(ll-rr)>eps)
{
R double mid=(ll+rr)/2;
if(ok(mid))ll=mid;
else rr=mid;
}
printf("%.2f",ll);
}
```