【题目描述】

　　　　一个点每过一个单位时间就会向 4 个方向扩散一个距离，如图所示：两个点 a 、b 连通，记作 e(a,b)，当且仅当 a 、b 的扩散区域有公共部分。连通块的定义是块内的任意两个点 u、v 都必定存在路径 $\mathrm{e(u,a0),e(a0,a1),\dots e(ak,v)。}$

　　　　给定平面上的 n 个点，问最早什么时候它们形成一个连通块。

【题目链接】

　　　　https://loj.ac/problem/10015

【算法】

　　　　正向做比较复杂，考虑从答案+判定角度出发，使用二分。无向图联通性可以用并查集/dfs/floyd，并查集比较好写点。。。

【代码】

1 #include 
     
       2 #define P pair
      
        3 using namespace std; 4 int n; 5 int fa[100]; 6 P p[100]; 7 inline void read(int& x) { 8     char c; int a=0; 9     while(c=getchar(),c<'0'||c>'9'); a=a*10+c-'0';10     while(c=getchar(),c<='9'&&c>='0') a=a*10+c-'0';11     x=a;12 }13 int Get(int x) {14     if(fa[x]==x) return x;15     return fa[x]=Get(fa[x]);16 }17 int calc(int x,int y) {18     return (abs(p[x].first-p[y].first)+abs(p[x].second-p[y].second)+1)>>1;19 }20 bool valid(int x) {21     for(int i=1;i<=n;i++) fa[i]=i;22     for(int i=1;i<=n;i++) {23         for(int j=1;j<=n;j++) {24             if(calc(i,j)<=x) fa[Get(i)]=Get(j);25         }26     }27     for(int i=1,rec=Get(1);i<=n;i++) if(Get(i)!=rec) return false;28     return true;29 }30 int main() {31     read(n);32     for(int i=1;i<=n;i++) read(p[i].first),read(p[i].second);33     int l=0,r=2e9;34     while(l
       
        >1;36         if(valid(mid)) r=mid;37         else l=mid+1;38     }39     printf("%d\n",l);40     return 0;41 }