思路与算法

时刻t，一个点能到达曼哈顿距离≤t的区域。两个扩散区相交当且仅当两中心的曼哈顿距离≤2t，所以点对最早连通时间为ceil(distance/2)。将各点看作完全图顶点、该时间为边权，使用朴素Prim得到最小生成树，输出树上最大边权。

正确性说明

两曼哈顿球相交的必要性由三角不等式得到，充分性可以沿两点间的一条最短格路划分长度≤t的两段。于是时刻t的连通图恰好由权值≤t的边构成。最小生成树的最大边是使图连通所需的最小瓶颈值：若有更小阈值已连通，跨该最大边割必存在更小边，可替换并降低树权和，矛盾。故输出即最早整体连通时刻。

复杂度

Prim每次扫描所有尚未选点并更新距离，时间O(n²)，读入与初始化O(n)，空间O(n)，不保存O(n²)边。n≤50，坐标至10^9，曼哈顿距离和向上取整使用long long。

易错点

相交时间要除2后向上取整，不是直接使用曼哈顿距离。n=1时已经连通，答案0。源样例含坐标0，而范围文字从1开始；参考程序同时支持，追加训练数据满足文字范围并保留公开样例。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> p(n);
    for (auto &v : p)
        cin >> v.first >> v.second;
    vector<long long> d(n, 1LL << 60);
    vector<bool> used(n);
    d[0] = 0;
    long long ans = 0;
    for (int t = 0; t < n; ++t) {
        int u = -1;
        for (int i = 0; i < n; ++i)
            if (!used[i] && (u < 0 || d[i] < d[u]))
                u = i;
        used[u] = true;
        ans = max(ans, d[u]);
        for (int v = 0; v < n; ++v)
            if (!used[v])
                d[v] = min(d[v],
                           (llabs(p[u].first - p[v].first) + llabs(p[u].second - p[v].second) + 1) /
                               2);
    }
    cout << ans << '\n';
}