洛谷 P1661. 扩散

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int N = 100;
pair<int, int> point[N];
map<pair<int, int>, int> mp;
int n, tot, p[N];

int find(int x) {
    return p[x] == x ? p[x] : p[x] = find(p[x]);
}

void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) {
        p[px] = py;
    }
}

bool check(int t) {
    for (int i = 1; i <= tot; i++) p[i] = i;

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int dis = abs(point[i].x - point[j].x) + abs(point[i].y - point[j].y);
            if (dis <= 2 * t) {
                merge(mp[point[i]], mp[point[j]]);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= tot; i++) {
        if (p[i] == i) ans++;
    }

    return ans == 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> point[i].x >> point[i].y;
        if (mp.count(point[i]) == 0) {
            mp[point[i]] = ++tot;
        }
    }

    int l = 1, r = 1e9;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;

    return 0;
}