C++(clang++11) 解法, 执行用时: 510ms, 内存消耗: 4348K, 提交时间: 2020-12-20 18:17:31

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ---------------------- "<<endl
#define uint unsigned int
#define ULL unsigned long long
#define DB double
#define LDB long double
#define pii pair<int,int>
#define mpt make_pair
#define pb push_back
#define fr first
#define sc second
inline LL read(){
	LL nm=0; bool fh=true; char cw=getchar();
	for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
	return fh?nm:-nm;
}
#define M 100200
#define INF 2000000000
int n,ans=INF,rem,Mn,Mx;
int ls[M],rs[M],tot;
struct PT{
	int p[2];
	inline void gtin(){p[0]=read(),p[1]=read();}
}a[M],mn[M],mx[M],T[M];
inline bool cmp(PT a,PT b){return a.p[rem]<b.p[rem];}
inline void chkmn(int &x,int y){x=(x<y)?x:y;}
inline void chkmx(int &x,int y){x=(x>y)?x:y;}
inline void pushup(int x){
	if(ls[x]){
		chkmn(mn[x].p[0],mn[ls[x]].p[0]),chkmx(mx[x].p[0],mx[ls[x]].p[0]);
		chkmn(mn[x].p[1],mn[ls[x]].p[1]),chkmx(mx[x].p[1],mx[ls[x]].p[1]);
	}
	if(rs[x]){
		chkmn(mn[x].p[0],mn[rs[x]].p[0]),chkmx(mx[x].p[0],mx[rs[x]].p[0]);
		chkmn(mn[x].p[1],mn[rs[x]].p[1]),chkmx(mx[x].p[1],mx[rs[x]].p[1]);
	}
}
inline void build(int x,int l,int r,int dep){
	int mid=(l+r)>>1; rem=dep&1;
	nth_element(a+l,a+mid,a+r+1,cmp),T[x]=a[mid];
	if(l<mid) build(ls[x]=++tot,l,mid-1,dep+1);
	if(mid<r) build(rs[x]=++tot,mid+1,r,dep+1);
	mn[x]=mx[x]=T[x],pushup(x);
}
inline int Getdis(PT x,PT y){return abs(x.p[0]-y.p[0])+abs(x.p[1]-y.p[1]);}
inline int calcmn(int x,PT now){
	int res=0;
	if(mn[x].p[0]>now.p[0]) res+=mn[x].p[0]-now.p[0];
	if(mx[x].p[0]<now.p[0]) res+=now.p[0]-mx[x].p[0];
	if(mn[x].p[1]>now.p[1]) res+=mn[x].p[1]-now.p[1];
	if(mx[x].p[1]<now.p[1]) res+=now.p[1]-mx[x].p[1];
	return res;
}
inline int calcmx(int x,PT now){return max(abs(mn[x].p[0]-now.p[0]),abs(mx[x].p[0]-now.p[0]))+max(abs(mn[x].p[1]-now.p[1]),abs(mx[x].p[1]-now.p[1]));}
inline void Getmn(int x,PT now){
	if(calcmn(x,now)>Mn) return; int remdis=Getdis(T[x],now); if(remdis) Mn=min(Mn,remdis);
	if(ls[x]) Getmn(ls[x],now); if(rs[x]) Getmn(rs[x],now);
}
inline void Getmx(int x,PT now){
	if(calcmx(x,now)<Mx) return;
	Mx=max(Mx,Getdis(T[x],now));
	if(ls[x]) Getmx(ls[x],now); if(rs[x]) Getmx(rs[x],now);
}

int main(){
	n=read(); for(int i=1;i<=n;i++) a[i].gtin();
	build(tot=1,1,n,1);
	for(int i=1;i<=n;i++) Mn=INF,Mx=0,Getmn(1,a[i]),Getmx(1,a[i]),ans=min(ans,Mx-Mn);//debug(i)sp,debug(Mn)sp,debug(Mx)el;
	printf("%d\n",ans);
	return 0;
}