一个点每过一个单位时间就会向 444 个方向扩散一个距离，如图所示：两个点 a 、b 连通，记作 e(a,b)，当且仅当 a 、b的扩散区域有公共部分。连通块的定义是块内的任意两个点 u、v都必定存在路径 e(u,a0),e(a0,a1),…e(ak,v)。
给定平面上的 n 个点，问最早什么时候它们形成一个连通块。
第一行一个数 nnn ，以下 nnn 行，每行一个点坐标。
输出仅一个数，表示最早的时刻所有点形成连通块。
2
0 0
5 55对于 20% 的数据，满足 1≤n≤5,1≤Xi,Yi≤50;
对于 100%的数据，满足 1≤n≤50,1≤Xi,Yi≤10^9。
强行二分答案。
每次暴力枚举两个点，判断在当前时间是否接通了，如果接通了就在并查集里连接。
然后判断是否在同一个祖先之下，如果不在就调大时间，否则调小。
其实可以直接按两点距离从小到大去枚举边，如果枚举到一条边使在同一个祖先下，就找到了。
1 /*
2 编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
3 #222995
4 #10015. 「一本通 1.2 练习 2」扩散
5 Accepted 100 31 ms 252 KiB C++ / 1011 B qwerta 2018-10-09 8:59:31
6 */
7 #include<iostream>
8 #include<cstdlib>
9 #include<cstdio>
10 #include<cmath>
11 using namespace std;
12 struct emm{
13 int x,y;
14 }a[53];
15 int dis[53][53];
16 int n;
17 int fa[53];
18 int fifa(int x)
19 {
20 if(fa[x]==x)return x;
21 return fa[x]=fifa(fa[x]);
22 }
23 inline bool con(int x,int y)
24 {
25 int u=fifa(x),v=fifa(y);
26 if(u==v)return 0;
27 fa[u]=v;
28 return 1;
29 }
30 void erfen(int l,int r)
31 {
32 if(l+1==r){cout<<r;exit(0);}
33 int mid=(l+r)>>1;
34 for(int i=1;i<=n;++i)
35 fa[i]=i;
36 int k=n;
37 for(int i=1;i<=n;++i)
38 for(int j=i+1;j<=n;++j)
39 {
40 if(dis[i][j]<=mid*2)
41 {
42 if(con(i,j))k--;
43 }
44 }
45 if(k==1)erfen(l,mid);
46 else erfen(mid,r);
47 }
48 int main()
49 {
50 scanf("%d",&n);
51 if(n==1){cout<<0;return 0;}
52 for(int i=1;i<=n;++i)
53 scanf("%d%d",&a[i].x,&a[i].y);
54 for(int i=1;i<=n;++i)
55 for(int j=i+1;j<=n;++j)
56 dis[i][j]=dis[j][i]=abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y);
57 erfen(0,2e9);
58 return 0;
59 }
转载于:https://www.cnblogs.com/qwerta/p/9802282.html