题目大意

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

两个点 a , b a,b a,b 连通，记作 e ( a , b ) e(a,b) e(a,b)，当且仅当 a , b a,b a,b 的扩散区域有公共部分。

连通块的定义是块内的任意两个点 u , v u,v u,v 都必定存在路径 e ( u , a 0 ) , e ( a 0 , a 1 ) , … , e ( a k , v ) e(u,a0),e(a0,a1),…,e(ak,v) e(u,a0),e(a0,a1),…,e(ak,v)。

给定平面上的 n n n 给点，问最早什么时刻它们形成一个连通块。

对于 100 % 100\% 100% 的数据，满足 1 ≤ n ≤ 2000 , 1 ≤ X [ i ] , Y [ i ] ≤ 1 0 9 1≤n≤2000,1≤X[i],Y[i]≤10^9 1≤n≤2000,1≤X[i],Y[i]≤109。

解题思路

曼哈顿距离应该都懂的。

易得两个点联通，需要 ( ⌊ ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ 2 ⌋ ) + ( ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ )   m o d   2 ) (\left\lfloor\frac{|x_1-x_2|+|y_1-y_2|}{2}\right\rfloor) + (|x_1-x_2|+|y_1-y_2|)\bmod 2) (⌊2∣x1​−x2​∣+∣y1​−y2​∣​⌋)+(∣x1​−x2​∣+∣y1​−y2​∣)mod2) （前面算的是余数）。

故可设任意两点之间的距离为上面那个式子，跑一边最小生成树，求出最小生成树上最长的边，即为答案。

AC CODE

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define _ 400007

int n;

int xx[_], yy[_];

int ans;

int tot;

struct abc
{
	int x, y, dis;
} e[4000007];

int fa[_];

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

bool cmp(abc a, abc b)
{
	return a.dis < b.dis;
}

void kruskal()
{
	sort(e + 1, e + tot + 1, cmp);
	for(int i = 1; i <= n; ++i) fa[i] = i;
	int kkk = 0;
	for(int i = 1; i <= tot; ++i)
	{
		int xx = find(e[i].x), yy = find(e[i].y);
		if(xx != yy)
		{
			fa[yy] = xx;
			kkk++;
			ans = max(ans, e[i].dis);
			if(kkk == n - 1) return;
		}
	}
}

signed main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cin >> xx[i] >> yy[i];
	}
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j < i; ++j)
		{
			int op = abs(xx[i] - xx[j]) + abs(yy[i] - yy[j]);
			e[++tot].x = i;
			e[tot].y = j;
			e[tot].dis = (op / 2) + (op & 1);
		}
	}
	kruskal(); 
	cout << ans << "\n";
	return 0;
}