K 联合狩猎

对于曼哈顿距离有一个关键性质 对每个点 ，定义 ，则任意两点间有

所以一个点集的曼哈顿直径为

也就是说一个集合的曼哈顿直径 ，等价于它在 平面里横纵两个方向的跨度都 。

题目要把所有点分成两个非空集合，使得两个集合的直径都 。

在 平面里，这等价于：

每个集合都能被一个边长为 的正方形装下；要把所有点分成两个这样的集合。

所以只要能判断 是否可行，就可以二分最小答案。

如何 check？

先求出所有点的 ，然后枚举四个角，这里以左下角为例，把 或 ，即靠近左边界，或者靠近下边界的点，都归到这一组。然后检查组内 跨度是否都 ，若满足则该 可行。依次检查四个角即可。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+10;
int n,a[N],b[N];
bool check(ll D) {
	int minA=*min_element(a, a+n);
	int maxA=*max_element(a, a+n);
	int minB=*min_element(b, b+n);	
	int maxB=*max_element(b, b+n);
	if (maxA - minA <= D && maxB - minB <= D) return 1;
	{
		int rminA = 1e9, rmaxA = -1e9, rminB = 1e9, rmaxB = -1e9;
		bool has = 0;		
		for (int i = 0; i < n; ++i) {			
			if (a[i] > minA + D || b[i] > minB + D) {			
				has = 1;			
				rminA = min(rminA, a[i]); rmaxA = max(rmaxA, a[i]);			
				rminB = min(rminB, b[i]); rmaxB = max(rmaxB, b[i]);			
			}
		}
		if (has && rmaxA - rminA <= D && rmaxB - rminB <= D) return 1;	
	}	
	{
		int rminA = 1e9, rmaxA = -1e9, rminB = 1e9, rmaxB = -1e9;	
		bool has = 0;
		for (int i = 0; i < n; ++i) {		
			if (a[i] > minA + D || b[i] < maxB - D) {			
				has = 1;			
				rminA = min(rminA, a[i]); rmaxA = max(rmaxA, a[i]);		
				rminB = min(rminB, b[i]); rmaxB = max(rmaxB, b[i]);			
			}	
		}
		if (has && rmaxA - rminA <= D && rmaxB - rminB <= D) return 1;	
	}
	{	
		int rminA = 1e9, rmaxA = -1e9, rminB = 1e9, rmaxB = -1e9;		
		bool has = 0;	
		for (int i = 0; i < n; ++i) {	
			if (a[i] < maxA - D || b[i] > minB + D) {	
				has = 1;	
				rminA = min(rminA, a[i]); rmaxA = max(rmaxA, a[i]);
				rminB = min(rminB, b[i]); rmaxB = max(rmaxB, b[i]);
			}
		}
		if (has && rmaxA - rminA <= D && rmaxB - rminB <= D) return 1;	
	}
	{
		int rminA = 1e9, rmaxA = -1e9, rminB = 1e9, rmaxB = -1e9;	
		bool has = 0;	
		for (int i = 0; i < n; ++i) {	
			if (a[i] < maxA - D || b[i] < maxB - D) {		
				has = 1;	
				rminA = min(rminA, a[i]); rmaxA = max(rmaxA, a[i]);	
				rminB = min(rminB, b[i]); rmaxB = max(rmaxB, b[i]);	
			}
		}
		if (has && rmaxA - rminA <= D && rmaxB - rminB <= D) return 1;	
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		a[i] = x + y;	
		b[i] = x - y;
	}
	int l = 0, r = 400000; 
	while (l < r) {	
		ll mid = (r + l) / 2;	
		if (check(mid)) r = mid;		
		else l = mid + 1;	
	}
	cout << l;
	return 0;
}