思路:二分,每次枚举2个角覆盖掉,然后判断能否用第三个L*L覆盖.

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,l=0,r=2100000000,mid;
struct pt{
	int x,y,f;
}a[1000005];
bool inrange(int a,int b,int x){return a<=x&&x<=b;}
void cover(int x,int y,int l){//覆盖,O(n)
	int x2=x+l,y2=y+l;
	for(int i=1;i<=n;i++)if(inrange(x,x2,a[i].x)&&inrange(y,y2,a[i].y))a[i].f=1;
}
void reset(){for(int i=1;i<=n;i++)a[i].f=0;}//设为未覆盖
bool check(){for(int i=1;i<=n;i++)if(a[i].f==0)return false;return true;}//检查
void update(int&x,int&b,int&c,int&d,int ind){
	if(a[ind].f!=0)return;
	x=max(x,a[ind].x);b=min(b,a[ind].x);c=max(c,a[ind].y);d=min(d,a[ind].y);
}//更新
bool ccover(int len){
	if(check())return true;
	int maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;
	for(int i=1;i<=n;i++)update(maxx,minx,maxy,miny,i);
	if(max(maxx-minx,maxy-miny)<=len)return true;
	return false;
}//能否覆盖
void cal(int&a,int&b,int&c,int &d){
	//+x,,-x,+y,-y
	for(int i=1;i<=n;i++)update(a,b,c,d,i);
}//计算左上,右上,左下,右下
bool chk(int mid){//真正的check
	int maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;
	cal(maxx,minx,maxy,miny);
	//A.B
	//...
	//C.D
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,miny,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,miny,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,miny,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,maxy-mid,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,miny,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,maxy-mid,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,miny,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,maxy-mid,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,miny,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,maxy-mid,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,maxy-mid,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,maxy-mid,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,miny,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,miny,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,maxy-mid,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,miny,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,maxy-mid,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,miny,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,maxy-mid,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,miny,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,maxy-mid,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,miny,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,maxy-mid,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,maxy-mid,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,miny,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,miny,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,maxy-mid,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,maxy-mid,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,miny,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(maxx-mid,miny,mid);
	if(ccover(mid))return true;
	reset();maxx=-2e9,minx=2e9,maxy=-2e9,miny=2e9;if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,maxy-mid,mid);if(ccover(mid))return true;cal(maxx,minx,maxy,miny);
	cover(minx,maxy-mid,mid);
	if(ccover(mid))return true;//16个角,WC
	return false;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	while(l<r){
		mid=(l+r)>>1;
		if(chk(mid))r=mid;
		else l=mid+1;
	}
	cout<<r;
}