题意

给定$n$个点，问能用三个正方形完全覆盖所有的点时正方形的边长最小是多少

$n <= 20000$

$-1e9<=x_i,y_i<=1e9$

做法

这个题显然是二分边长，难点在于$check$怎么写

三个正方形可能不好想，所以我们可以先考虑小问题，一个正方形应该怎么想，显然是放在四个角中的一个，那么两个正方形呢，可以先放一个正方形在四个角，然后再用另一个正方形放在删完之后的角上去判，三个同理

时间复杂度$O(4^3nlogn)$

其实这个题中的三可以改为$k$

这样的话复杂度就是$O(4^knlogn)$

code

#include <bits/stdc++.h>
using namespace std;

const int inf = 2e9 + 1;

const int N = 2e5 + 1;

int n, x[N], y[N];

int a[2], b[2];
//读入 
void read() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
	}
}

int vis[N];

int d[4][2] = {{0,0},{0,1},{1,0},{1,1}};
//删 
void del(int xx,int yy,int len,int id) {
	if(xx == 0 && yy == 0) {
		xx = a[xx];
		yy = b[yy];
		for(int i = 1; i <= n; i++) {
			if(!vis[i]&&x[i]-xx<=len&&y[i]-yy<=len)
				vis[i] = id;
		}
	}
	if(xx == 1 && yy == 0) {
		xx = a[xx];
		yy = b[yy];
		for(int i = 1; i <= n; i++) {
			if(!vis[i]&&-x[i]+xx<=len&&y[i]-yy<=len)
				vis[i] = id;
		}
	}
	if(xx == 1 && yy == 1) {
		xx = a[xx];
		yy = b[yy];
		for(int i = 1; i <= n; i++) {
			if(!vis[i]&&-x[i]+xx<=len&&-y[i]+yy<=len)
				vis[i] = id;
		}
	}
	if(xx == 0 && yy == 1) {
		xx = a[xx];
		yy = b[yy];
		for(int i = 1; i <= n; i++) {
			if(!vis[i]&&x[i]-xx<=len&&-y[i]+yy<=len)
				vis[i] = id;
		}
	}
}
//回溯 
void rem(int id) {
	for(int i = 1; i <= n; i++) {
		if(vis[i] == id) vis[i] = 0;
	}
	return ;
}
//判是否删完 
bool www() {
	int ans = 1;
	for(int i = 1; i <= n; i++) {
		ans &= (bool)vis[i];
		if(ans == 0) return 0;
	}
	return 1;
}
//找现存的四个角 
void find() {
	a[0] = b[0] = inf;
	a[1] = b[1] = -inf;
	for(int i = 1; i <= n; i++) {
		if(vis[i]) continue;
		a[0] = min(a[0],x[i]);
		b[0] = min(b[0],y[i]);
		a[1] = max(a[1],x[i]);
		b[1] = max(b[1],y[i]);
	}
	return ;
}
//check 
bool check(int len,int id) {
	if(www()) {
		return 1;
	} else if(id == 0) return 0;
	bool ans = 0;
	for(int i = 0; i < 4; i++) {
		find();
		del(d[i][0],d[i][1],len,id);
		ans |= check(len,id-1);
		rem(id);
	}
	return ans;
}
//二分 
void compute() {
	int l = 0,r = inf, ans;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid,3)) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	cout << ans ;
	return ;
}
//主函数 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}