看到这道题，思考一下后发现要用二分答案。所以为什么要用二分？
因为标签有二分还在二分专题里
因为对于 \(ans\) 来说，如果 \(ans\) 不行，那么 \(ans-1\) 也一定不行；也就是说，答案满足单调性，所以可以二分；
也是因为暴力明显过不了
那么对于平面上的一些点来说，如果我们用一个最小的矩形覆盖所有点，那么这个矩形的大小和位置都是固定的；
所以我们的目标就是三个等大的小正方形替换它，并保证所有点仍被覆盖；
由于小正方形的边与坐标轴平行，而这个最小的矩形的每个边上都至少有一个点（否则不满足“最小”），所以每个小正方形一定至少有一条边与大长方形重合；
而由于我们只有三个正方形，所以一定有一个正方形在角上；
到这里，思路已经很清晰了：
二分小正方形边长，dfs 四个角的四种情况，得出答案
完整代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4+5;
const int inf=0x7fffffff;
struct tree{
int x,y,now;
bool operator < (const tree &a)const{//优先按照 x 升序，x 相等按 y 升序
if(x==a.x)return y<a.y;
return x<a.x;
}
}a[N];
int n,maxn;
void cap(int minx,int maxx,int miny,int maxy,int now){//对指定区间进行覆盖，now记录当前是第几块塑料布
for(int i=1;i<=n;i++){
if(a[i].now)continue;
if(minx<=a[i].x&&a[i].x<=maxx&&miny<=a[i].y&&a[i].y<=maxy)
a[i].now=now;
}
}
void recap(int now){//取消点当前的now标记 （之前的不会清空）
for(int i=1;i<=n;i++){
if(a[i].now==now)a[i].now=0;
}
}
bool dfs(int now,int mid){
int minx=inf,maxx=-inf;
int miny=inf,maxy=-inf;
for(int i=1;i<=n;i++){
if(!a[i].now){//在未被覆盖的点中寻找最大与最小 x y 坐标
maxx=max(maxx,a[i].x);
minx=min(minx,a[i].x);
maxy=max(maxy,a[i].y);
miny=min(miny,a[i].y);
}
}
int lenx=maxx-minx;
int leny=maxy-miny;
if(max(lenx,leny)<=mid)return 1;//能够覆盖
if(now==3)return 0;//塑料布用完了
cap(minx,minx+mid,miny,miny+mid,now);//左下角
if(dfs(now+1,mid))return 1;//寻找下一块
recap(now);//回溯
cap(minx,minx+mid,maxy-mid,maxy,now);//左上角
if(dfs(now+1,mid))return 1;
recap(now);
cap(maxx-mid,maxx,miny,miny+mid,now);//右下角
if(dfs(now+1,mid))return 1;
recap(now);
cap(maxx-mid,maxx,maxy-mid,maxy,now);//右上角
if(dfs(now+1,mid))return 1;
recap(now);
return 0;
}
bool check(int x){
for(int i=1;i<=n;i++)a[i].now=0;//清空覆盖状态
return dfs(1,x);//dfs
}
int solve(int l,int r){//喜欢打递归版的二分答案
int mid=(l+r)>>1;
if(r<=l)return mid;
if(check(mid))return solve(l,mid);
else return solve(mid+1,r);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+1+n);//记得排序
cout<<solve(1,inf);
return 0;
}