#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 2e4 + 10;
const LL inf = 2000000010LL;   // 极限（ 1e9+10 不够大，因为坐标差可达 2e9）
 
struct Point {
	LL x, y;
} a[N];
 
int n;
int v[N];  // 标记每个点是否被覆盖（0=未覆盖）
 
bool dfs(LL k, int id) {
	if (id == 4) {     // 三个小正方形全部完成 
		for (int i = 1; i <= n; i ++) {
			if (!v[i]) {
				return 0;
			}
		}
		return 1;
	}
	
	LL mnx = inf, mxx = -inf;
	LL mny = inf, mxy = -inf;
	for (int i = 1; i <= n; i ++) if (!v[i]) {
		mnx = min(mnx, a[i].x);
		mxx = max(mxx, a[i].x);
		mny = min(mny, a[i].y);
		mxy = max(mxy, a[i].y);
	} 
	if (mnx == inf) {    // 全都覆盖了 
		return 1;
	}
	
	// 把紧贴着四个角的小正方形放进去 
	// 每个正方形用 pair<Point, Point> 表示：first 是左下角，second 是右上角
	vector<pair<Point, Point>> conner;
	conner.push_back({{mnx, mny}, {mnx + k, mny + k}});     // 左下角对齐
	conner.push_back({{mnx, mxy - k}, {mnx + k, mxy}});     // 左上角对齐
	conner.push_back({{mxx - k, mny}, {mxx, mny + k}});     // 右下角对齐
	conner.push_back({{mxx - k, mxy - k}, {mxx, mxy}});     // 右上角对齐
	
	bool flag = 0;   // 当前循环是否有解 
	for (auto i : conner) {
		LL lx = i.first.x, rx = i.second.x;
		LL ly = i.first.y, ry = i.second.y;
		
		// 保存当前状态，用于回溯
		vector<int> bak(v + 1, v + n + 1);
		
		for (int j = 1; j <= n; j ++) if (!v[j]) {
			if (a[j].x >= lx && a[j].x <= rx && a[j].y >= ly && a[j].y <= ry) { 
				v[j] = id;    // 在范围内就可以覆盖到 
			}
		}
		flag |= dfs(k, id + 1);    // 遍历下一个小正方形 
		
		// 回溯：恢复 v 数组
		for (int j = 1; j <= n; j++) {
			v[j] = bak[j - 1];
		}
		
		if (flag) {
			break; // 提前终止（可选优化）
		}
	}
	return flag;
}
 
bool check(LL k) {     // 返回 1 是成功 
	memset(v, 0, sizeof(v));    // 所有点都是未覆盖状态 
	return dfs(k, 1);   // 递归边长与小正方形编号 
}
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].x >> a[i].y;
	}
	
	LL l = 0, r = 2000000000LL, p = 0;     // 二分枚举小正方形边长
	// 边长最小可以是 0（所有点重合的情况） 
	while (l <= r) {
		LL mid = (l + r) >> 1;
		if (check(mid)) {
			r = mid - 1;
			p = mid;
		}
		else {
			l = mid + 1;
		}
	} 
	cout << p << "\n";
	
	return 0;
}

https://blog.csdn.net/tenkuo/article/details/153773615