题目描述：
Hy又即将踏上拯救公主的道路……
这次的拯救目标是——爱和正义的公主。
Hy来到boss的洞穴门口，他一下子就懵了，因为面前不只是一只boss，而是上千只boss。当英雄意识到自己还是等级1的时候，他明白这就是一个不可能完成的任务。
但他不死心，他在想，能不能避开boss去拯救公主呢，嘻嘻。
Boss的洞穴可以看成一个矩形，英雄在左下角（1,1），公主在右上角（row，line）。Hy为了避开boss，当然是离boss距离越远越好了，所以英雄决定找一条路径使到距离boss的最短距离最远。
Ps:Hy走的方向是任意的。
你可以帮帮Hy吗？
当Hy找到了美丽漂亮的公主，立刻就被boss包围了！！！英雄缓闭双眼，举手轻挥，白光一闪后使用了回城卷轴，回到了城堡，但只有公主回去了……因为Hy忘了进入回城的法阵了。
输入：
第一行，输入三个整数，n表示boss的数目，row，line表示矩形的大小；
接下来n行，每行分别两个整数表示boss的位置坐标。
输出：
输出一个小数，表示英雄的路径离boss的最远距离，精确到小数点后两位。
数据范围：
20%数据，boss坐标范围小于等于50；
60%数据，n<=1500；
100%数据，n<=3000；row,line小于等于30000；
算法标签：二分、并查集/最小生成树kruskal(此篇题解是kruskal的方法)
思路：
首先转换思路，由王子救公主的路径的最远距离转化成boss能拦住王子的最小距离，由此我们可以发现当由各个boss组成的联通快同时碰到左下和右上的墙壁时，王子无路可走。于是我们n2处理两两boss之间距离，以及boos和两壁之间的距离，然后最小生成树，当两个壁在同一个联通块时，统计答案。
以下代码：
#include<bits/stdc++.h> #define il inline #define D double #define LL long long #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=3005,M=9e6+5;int n,row,line,x[N],y[N],fa[N],tot; struct node{int l,r;D len;}t[M]; il int read(){int x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch^48;_()x=(x<<1)+(x<<3)+(ch^48);return f*x;} il LL dis(int a,int b){return (LL)(y[a]-y[b])*(LL)(y[a]-y[b])+(LL)(x[a]-x[b])*(LL)(x[a]-x[b]);} il int getfa(int x){if(!fa[x])return x;return fa[x]=getfa(fa[x]);} bool cmp(node t1,node t2){return t1.len<t2.len;} il LL p(LL x){return x*x;} int main() { n=read();row=read();line=read(); for(int i=1;i<=n;i++)x[i]=read(),y[i]=read(); for(int i=1;i<=n;i++)for(int j=1;j<i;j++)t[++tot]=(node){i,j,dis(i,j)}; for(int i=1;i<=n;i++){ t[++tot]=(node){i,n+1,(D)p((LL)min(row-x[i],y[i]-1)*2ll)}; t[++tot]=(node){i,n+2,(D)p((LL)min(line-y[i],x[i]-1)*2ll)}; } sort(t+1,t+1+tot,cmp); for(int i=1;i<=tot;i++){ int x=getfa(t[i].l),y=getfa(t[i].r); if(x==y)continue; fa[x]=y;if(getfa(n+1)==getfa(n+2)){printf("%.2lf ",sqrt(t[i].len)*0.5);break;} } return 0; }