P1661 扩散（二分+并查集）

题目描述

一个点每过一个单位时间就会向四个方向扩散一个距离，如图。

两个点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。

输出格式

一个数，表示最早的时刻所有点形成连通块。

输入输出样例

输入 #1

2
0 0
5 5

输出 #1

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
",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 }

View Code