【题目来源】
洛谷：P1661 扩散 - 洛谷
【题目描述】
一个点每过一个单位时间就会向四个方向扩散一个距离，如图。
两个点 \(a\) 、 \(b\) 连通，记作 \(e(a,b)\)，当且仅当 \(a,b\) 的扩散区域有公共部分。连通块的定义是块内的任意两个点 \(u,v\) 都必定存在路径 \(e(u,a_0),e(a_0,a_1),\cdots,e(a_k,v)\)。给定平面上的 \(n\) 个点，问最早什么时刻它们形成一个连通块。
【输入】
第一行一个数 \(n\)，以下 \(n\) 行，每行一个点坐标。
【输出】
一个数，表示最早的时刻所有点形成连通块。
【输入样例】
2
1 1
6 6
【输出样例】
5
【算法标签】
《洛谷 P1661 扩散》 #图论# #树形数据结构# #二分# #并查集# #生成树#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 55;int n, p[N];
struct Node
{int x, y;
} a[N];// 并查集查找操作
int find(int x)
{if (p[x] != x){p[x] = find(p[x]);}return p[x];
}// 检查是否能在半径为x的范围内建立连接，使所有点连通
bool check(int x)
{for (int i = 1; i <= n; i++){p[i] = i; // 初始化并查集}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (i == j){continue;}// 计算曼哈顿距离int dist = (abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y));// 如果两个点之间的距离不超过2x，可以建立连接if (dist <= x * 2){int a = find(i), b = find(j);if (a != b){p[a] = b; // 合并连通块}}}}int root = find(1);// 检查是否所有点都在同一个连通块中for (int i = 2; i <= n; i++){if (find(i) != root){return false;}}return true;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].x >> a[i].y;}// 二分查找最小的半径xint l = 0, r = 1e9;while (l < r){int mid = (l + r) / 2;if (check(mid)){r = mid; // 满足条件，尝试更小的半径}else{l = mid + 1; // 不满足条件，需要更大的半径}}cout << l << endl;return 0;
}
【运行结果】
2
1 1
6 6
5