P1661 扩散

P1661 扩散

题目分析：

1. 求解最早的时刻所有点形成连通块
2. 连通块需要用到并查集，时间从小到大符合单调用二分
3. 答案区间[l,r] (l = 1,r = inf)

代码如下：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

#define inf 0x3f3f3f3f
#define eps 1e-6
#define db double
#define ll long long
#define  mm(a,x) memset(a,x,sizeof a)
#define pii pair<int,int>
#define pb push_back
#define el endl
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define fgx cerr<<"-------------------------"<<endl
#define shutio ios::sync_with_stdio(false),cin.tie(0)
#define  mk make_pair
#define lowbit(x) (x) & (-x)
#define fi first
#define se second

const int N = 100;

int n;
pii node[N];
int fa[N];
int l,r;

void init(){
    for(int i = 1; i <= n; i ++ ) fa[i] = i;
}

int find(int x){
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void merge(int a,int b){
    fa[find(a)] = find(b);    
}

bool check(int x){
    init();
    for(int i = 1; i <= n; i ++ ){
        for(int j = i + 1; j <= n; j ++ ){
            ll dist = abs(node[i].fi - node[j].fi) + abs(node[i].se - node[j].se);
            if(dist <= 2 * x){
                merge(i,j);
            }
        }
    }
    set<int > s;
    for(int i = 1; i <= n; i ++ ) s.insert(find(fa[i]));
    if(s.size() == 1) return true;
    else return false;        
}

int main() {
    shutio;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        int a,b; cin >> a >> b;
        node[i] = {a,b};
    }
    l = 1,r = inf;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout<<l;            
    return 0;
}