一个点每过一个单位时间就会向四个方向扩散一个距离，如图。
两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。
第一行一个数n，以下n行，每行一个点坐标。
【数据规模】
对于20%的数据，满足1≤N≤5; 1≤X[i],Y[i]≤50;
对于100%的数据，满足1≤N≤50; 1≤X[i],Y[i]≤10^9。
一个数，表示最早的时刻所有点形成连通块。
2 0 0 5 5
5
解题思路： 只要找到两个点垂直距离+水平距离《=2*t 这两个点就会相遇（倍增 多试几个点就可以找到规律 ） 连通块首先想到并查集 然后二分时间求解就行了
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define eps 1e-6 5 using namespace std; 6 typedef long long ll; 7 8 int n; 9 ll x[55],y[55]; 10 ll arr[55]; 11 12 ll find_root(ll x){ 13 return arr[x]==x?x:arr[x]=find_root(arr[x]); 14 } 15 16 bool check(ll num){ 17 int ans=0; 18 for(int i=1;i<=n;i++) arr[i]=i; 19 for(int i=1;i<=n;i++){ 20 for(int j=i+1;j<=n;j++){ 21 if(abs(x[i]-x[j])+abs(y[i]-y[j])<=2*num){ //在num这个时间内能两个点能够相遇 22 ll xx=find_root(i); 23 ll yy=find_root(j); 24 arr[xx]=yy; ///要找根啊 25 } 26 } 27 } 28 for(int i=1;i<=n;i++){ 29 if(arr[i]==i) ans++; 30 } 31 if(ans==1) return true; 32 else return false; 33 } 34 35 void Dichotomy(){ 36 ll left=0,right=1e9; 37 ll ans; 38 while(left<=right){ 39 ll mid=left+right>>1; 40 if(check(mid)) right=mid-1,ans=mid; 41 else left=mid+1; 42 } 43 printf("%lld\n",ans); 44 } 45 46 int main(){ 47 scanf("%d",&n); 48 for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]); 49 Dichotomy(); 50 return 0; 51 }
原文：https://www.cnblogs.com/qq-1585047819/p/11256837.html
