假装是个计算几何，看到最远距离，考虑二分答案
二分一个答案后每个 $boss$ 就是圆，变成了问是否能够不经过圆从 $(1,1)$ 走到 $(n,m)$，即问 $(1,1)$ 和 $(n,m)$ 是否联通
满满的狼抓兔子既视感
考虑是否联通其实就是问是否有一些圆连在一起把左下到右上断开
所以考虑用并查集维护圆和边界之间的联通性，如果左上和右下被若干圆连接了，那么左下就无法走到右上
（好像直接 $prim$ 求最小生成树的做法不用二分答案...？反正都能过...）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; typedef double db; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const db eps=1e-7; const int N=3007; int n,fa[N]; db A,B,px[N],py[N]; inline int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]); } inline void merge(int x,int y) { if(find(x)!=find(y)) fa[find(x)]=find(y); } inline db Len(int i,int j) { return sqrt((px[i]-px[j])*(px[i]-px[j])+(py[i]-py[j])*(py[i]-py[j])); } bool check(db p) { for(int i=0;i<=n+1;i++) fa[i]=i; for(int i=1;i<=n;i++) { if(px[i]-p<=1||B<py[i]+p) merge(0,i); if(py[i]-p<=1||A<px[i]+p) merge(n+1,i); } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(Len(i,j)<p*2) merge(i,j); return find(0)!=find(n+1); } int main() { n=read(),A=read(),B=read(); for(int i=1;i<=n;i++) px[i]=read(),py[i]=read(); db L=0,R=min(A,B); while(L<=R) { db mid=(L+R)/2; if(check(mid)) L=mid+eps; else R=mid-eps; } printf("%.2f\n",L); return 0; }
原文：https://www.cnblogs.com/LLTYYC/p/11489622.html