https://zybuluo.com/ysner/note/1218481
题面
最小化(L),使(3)个(L×L)的正方形能覆盖图上(n)个点。
- (nleq20000,Lleq2*10^9)
解析
首先肯定要二分答案，(L)是算不出来的。
然后构建一个覆盖所有点的最小矩形。
注意到每条边至少要一个正方形靠着。
但现在只有(3)个正方形，意味着至少有一个正方形靠着两条边。
靠着相对的两条边？那说明这个图被这(3)个正方形并排着覆盖。
即一定存在靠着相邻两条边（在四角）的正方形。
可以把四种情况都试一遍。
用(1)个覆盖之后又可以重复上面的步骤，以此类推。
然而我因为各种愚蠢错误(WA)了一版，如开全局变量（开局部才能保证互不影响）、打错条件与数字。。。
复杂度上限(O(4^3nlogn))
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e4+100;
int n,x[N],y[N];
bool vis[N];
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int solve(re ll l,re ll r,re ll u,re ll d,re int t,re ll L)
{
re bool viss[N]={};fp(i,1,n) viss[i]=vis[i];
re int flag=1;
fp(i,1,n) if(!vis[i]) flag=0;
if(flag) return 1;
else if(t>3) return 0;
{
re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
fp(i,1,n) if(x[i]>=l&&y[i]>=d&&x[i]<=l+L&&y[i]<=d+L) vis[i]=1;
fp(i,1,n) if(!vis[i]) zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
if(solve(zz,yy,ss,xx,t+1,L)) return 1;
fp(i,1,n) vis[i]=viss[i];
}
{
re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
fp(i,1,n) if(x[i]>=l&&y[i]<=u&&x[i]<=l+L&&y[i]>=u-L) vis[i]=1;
fp(i,1,n) if(!vis[i]) zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
if(solve(zz,yy,ss,xx,t+1,L)) return 1;
fp(i,1,n) vis[i]=viss[i];
}
{
re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
fp(i,1,n) if(x[i]<=r&&y[i]>=d&&x[i]>=r-L&&y[i]<=d+L) vis[i]=1;
fp(i,1,n) if(!vis[i]) zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
if(solve(zz,yy,ss,xx,t+1,L)) return 1;
fp(i,1,n) vis[i]=viss[i];
}
{
re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
fp(i,1,n) if(x[i]<=r&&y[i]<=u&&x[i]>=r-L&&y[i]>=u-L) vis[i]=1;
fp(i,1,n) if(!vis[i]) zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
if(solve(zz,yy,ss,xx,t+1,L)) return 1;
return 0;
}
}
int main()
{
n=gi();
re int zz=1e9,xx=1e9,yy=-1e9,ss=-1e9;
fp(i,1,n) x[i]=gi(),y[i]=gi(),zz=min(zz,x[i]),yy=max(yy,x[i]),xx=min(xx,y[i]),ss=max(ss,y[i]);
re ll l=1,r=2e9,ans=1;
while(l<=r)
{
re ll mid=l+r>>1;
memset(vis,0,sizeof(vis));
if(solve(zz,yy,ss,xx,1,mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld
",ans);
return 0;
}