挺水的题...好多题解说是对偶图，其实感觉不能算严格意义上的对偶图吧QAQ
先二分答案r，然后以boss为中心半径为r的圆不能走，求能否从左下走到右上。
不能从左下走到右上，说明这堆圆把图隔开了，于是把圆看成点，如果两个圆有重合部分就连边，左上两条边界看成S，右下两条边界看成T，如果连边后S和T连通说明无法从左下走到右上，没了...
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; const int maxn=3010, inf=1e9; int n, N, M, S, T, tot, front, rear; int x[maxn], y[maxn], h[maxn], d[maxn][maxn], fa[maxn]; bool v[maxn]; inline void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline int sqr(int x) {return x*x;} inline int dis(int a, int b) {return 1ll*sqr(abs(x[a]-x[b]))+sqr(abs(y[a]-y[b]));} int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} inline bool check(double r) { for(int i=S;i<=T;i++) fa[i]=i; for(int i=1;i<=n;i++) { if(-(1e-6)<1.0+r-x[i] || y[i]+r-M>-(1e-6)) fa[gf(S)]=gf(i); if(x[i]+r-N>-(1e-6) || -(1e-6)<1.0+r-y[i]) fa[gf(T)]=gf(i); } if(gf(S)==gf(T)) return 0; for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(4ll*r*r>d[i][j]) { fa[gf(i)]=gf(j); if(gf(S)==gf(T)) return 0; } return 1; } int main() { read(n); read(N); read(M); S=0; T=n+1; for(int i=1;i<=n;i++) read(x[i]), read(y[i]); for(int i=1;i<=n;i++) for(int j=1;j<i;j++) d[i][j]=d[j][i]=dis(i, j); double l=0, r=min(N-1, M-1); while(r-l>1e-4) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.2lf ", l); }
还有就是完全可以不用二分，直接按边长度从小到大加入，当加入到S和T连通的时候当前边的长度-eps就是答案了。。。但是大概得写prim才能到N^2，不然kruskal比上面做法可能快不了多少，我不会prim就不写了QAQ
加强版需要三角剖分...不会.jpg