板子题，只是感觉KD-Tree写起来很爽就先找了道题写写，发现现在的手速越来越慢了的说
真没什么好说的，暴枚选那个点做起点，然后求到一个点的最远最近点即可
注意一个细节：判断一个点到矩形的距离最小值是要考虑仔细，某一维是否有贡献要看这个点是否被包含在最大最小的区间内（刚开始naive了）
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=2e9;
int D;
struct point
{
int d[2];
friend inline bool operator < (const point& A,const point& B)
{
return A.d[D]==B.d[D]?A.d[D^1]<B.d[D^1]:A.d[D]<B.d[D];
}
}a[N],s; int n,ans=INF,mi,mx,rt;
inline int dist(const point& A,const point& B)
{
return abs(A.d[0]-B.d[0])+abs(A.d[1]-B.d[1]);
}
class KD_Tree
{
private:
struct kd_interval
{
int ch[2]; point p,mi,mx;
}node[N]; int tot;
#define lc(x) node[x].ch[0]
#define rc(x) node[x].ch[1]
#define P(x) node[x].p
#define Mi(x) node[x].mi
#define Mx(x) node[x].mx
inline void pushup(CI x,CI y)
{
for (RI i=0;i<2;++i) Mi(x).d[i]=min(Mi(x).d[i],Mi(y).d[i]),
Mx(x).d[i]=max(Mx(x).d[i],Mx(y).d[i]);
}
inline int getmin(CI now)
{
if (!now) return INF; int cur=0;
for (RI i=0;i<2;++i) cur+=max(Mi(now).d[i]-s.d[i],0),cur+=max(s.d[i]-Mx(now).d[i],0);
return cur;
}
inline int getmax(CI now)
{
if (!now) return -INF; int cur=0;
for (RI i=0;i<2;++i) cur+=max(abs(Mi(now).d[i]-s.d[i]),abs(s.d[i]-Mx(now).d[i]));
return cur;
}
public:
inline void build(int& now,CI l=1,CI r=n,CI d=0)
{
now=++tot; int mid=l+r>>1; D=d; nth_element(a+l+1,a+mid+1,a+r+1);
P(now)=Mi(now)=Mx(now)=a[mid];
if (l!=mid) build(lc(now),l,mid-1,d^1),pushup(now,lc(now));
if (r!=mid) build(rc(now),mid+1,r,d^1),pushup(now,rc(now));
}
inline void querymin(CI now)
{
if (!now) return; if (getmin(now)>mi) return;
int tp=dist(s,P(now)); if (tp) mi=min(mi,tp);
int ml=getmin(lc(now)),mr=getmin(rc(now));
if (ml<mr) querymin(lc(now)),querymin(rc(now));
else querymin(rc(now)),querymin(lc(now));
}
inline void querymax(CI now)
{
if (!now) return; if (getmax(now)<mx) return;
int tp=dist(s,P(now)); mx=max(mx,tp);
int ml=getmax(lc(now)),mr=getmax(rc(now));
if (ml>mr) querymax(lc(now)),querymax(rc(now));
else querymax(rc(now)),querymax(lc(now));
}
#undef lc
#undef rc
#undef P
#undef Mi
#undef Mx
}KD;
int main()
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",&a[i].d[0],&a[i].d[1]);
for (KD.build(rt),i=1;i<=n;++i)
s=(point){a[i].d[0],a[i].d[1]},mi=INF,mx=-INF,KD.querymin(rt),KD.querymax(rt),ans=min(ans,mx-mi);
return printf("%d",ans),0;
}