[SWERC 2020] Safe Distance

題意

給定 $N$ 個點與一個坐標 $(X,Y)$，求從點 $(0,0)$ 到點 $(X,Y)$ 規劃一條路線，不能走出 $(0,0)$ 與 $(X,Y)$ 間形成的矩形，使得通過這條路線時距離最近的點的距離最遠，$N\le 1000$。

思路

不用二分也可以。

如果答案為 $x$，那么以每個點為圓心，半徑為 $x$ 作圓后，$(0,0)$ 與 $(X,Y)$ 一定連通。

怎樣連通不好想，可以想怎樣不連通。可以發現，不連通是一定時一些相交或相切的圓把網格堵住了，于是我們可以將相交或相切的點放在同一個并查集里。想象每個圓都在不斷變大，那么一定是圓心距離短的圓先相交或相切。我們給點兩兩建邊，邊權為兩點間的距離，把邊按照邊權從小到大排序，每次將邊的端點的并查集合并。因為左邊界與下邊界實際上是一個整體，上邊界與右邊界實際上是一個整體，所以如果某個邊加完后使得左邊界與下邊界、上邊界與右邊界在一個并查集里，那么這個邊權即為使得不連通的最小距離。答案理論上是這個最小距離減去極小的值，不過題目允許誤差，輸出這個值就可以。

代碼

#include<bits/stdc++.h>
using namespace std;
int x,y,n,cnt,fa[1005],s[1005];
double a[1005],b[1005];
int f(int x){if(fa[x]==x) return x;return fa[x]=f(fa[x]);
}
struct node{int u,v;double w;
}bian[2000005];
bool cmp(node x,node y)
{return x.w<y.w;
}
int main()
{scanf("%d%d%d",&x,&y,&n);for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i],&b[i]);for(int i=1;i<=n+2;i++) fa[i]=i,s[i]=1;//n+1為左邊界與下邊界的整體,n+2為右邊界與上邊界的整體for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++)bian[++cnt]={i,j,sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]))/2};//記得與上下左右邊界連邊bian[++cnt]={i,n+1,min(x-a[i],b[i])};bian[++cnt]={i,n+2,min(y-b[i],a[i])};}sort(bian+1,bian+1+cnt,cmp);for(int i=1;i<=cnt;i++){if(s[f(bian[i].u)]<s[f(bian[i].v)])s[f(bian[i].v)]+=s[bian[i].u],fa[f(bian[i].u)]=f(bian[i].v);elses[f(bian[i].u)]+=s[bian[i].v],fa[f(bian[i].v)]=f(bian[i].u);if(f(n+1)==f(n+2)){printf("%.6f",bian[i].w);return 0;}}return 0;
}