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的最远距离，精确到小数点后两位。
二分答案r，对每个点作半径r的圆，判断圆是否切断了(1,1)和(n,m)，即从左、上边界能否通过圆走到右/下边界
#include<cstdio>
#include<cmath>
#include<algorithm>
int n;
double xm,ym;
struct pos{double x,y;}ps[];
int q[],ed[];
bool discmp(double x,double y,double z){
return x*x+y*y<z*z;
}
bool chk(double R){
int ql=,qr=;
for(int i=;i<n;i++){
if(ps[i].x-<R||ps[i].y+R>ym){
q[qr++]=i;
ed[i]=;
if(ps[i].x+R>xm||ps[i].y-R<)return ;
}else ed[i]=;
}
while(ql!=qr){
int w=q[ql++];
for(int i=;i<n;i++)if(!ed[i]&&discmp(ps[i].x-ps[w].x,ps[i].y-ps[w].y,R*)){
q[qr++]=i;
ed[i]=;
if(ps[i].x+R>xm||ps[i].y-R<)return ;
}
}
return ;
}
int main(){
scanf("%d%lf%lf",&n,&xm,&ym);
for(int i=;i<n;i++){
scanf("%lf%lf",&ps[i].x,&ps[i].y);
}
double L=,R=xm+ym+;
while(R-L>1e-){
double M=(L+R)/.;
if(chk(M))R=M;
else L=M;
}
printf("%.2lf\n",(L+R)/.);
return ;
}
也可以用最小生成树的kruskal，加边直到发现第一条边使左、上边界与右、下边界连通
#include<cstdio>
#include<cmath>
#include<algorithm>
int n,xm,ym,ep=;
int f[];
struct pos{int x,y;}ps[];
struct edge{int a,b;long long c;}e[];
bool operator<(edge a,edge b){
return a.c<b.c;
}
inline long long min2(long long a,long long b){
a*=a;b*=b;
return a<b?a:b;
}
int get(int x){
int a=x,c;
while(x!=f[x])x=f[x];
while(x!=(c=f[a]))f[a]=x,a=c;
return x;
}
int main(){
scanf("%d%d%d",&n,&xm,&ym);
for(int i=;i<n;i++){
f[i]=i;
scanf("%d%d",&ps[i].x,&ps[i].y);
e[ep++]=(edge){i,n,*min2(xm-ps[i].x,ps[i].y-)};
e[ep++]=(edge){i,n+,*min2(ps[i].x-,ym-ps[i].y)};
for(int j=;j<i;j++){
long long x=ps[i].x-ps[j].x,y=ps[i].y-ps[j].y;
e[ep++]=(edge){i,j,x*x+y*y};
}
}
f[n]=n;f[n+]=n+;
std::sort(e,e+ep);
for(int i=;i<ep;i++){ int a=get(e[i].a),b=get(e[i].b);
if(a!=b){
f[a]=b;
if(get(n)==get(n+)){
printf("%.2f\n",sqrt(e[i].c)/.+1e-);
return ;
}
}
}
return ;
}