K-D Tree "模板题"（但是本蒟蒻找不出BUG啊啊啊

大意： 已知二维平面上 N 个整点。求其中一点，使其到其余点的最大曼哈顿距离减去最小曼哈顿距离的值最小，输出这个值。

提交记录

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
struct node{
	int x,y;
}s[maxn];
int n,ans=inf,maxd,mind,lc[maxn],rc[maxn],L[maxn],R[maxn],D[maxn],U[maxn];
inline bool cmpx(node x,node y) {return x.x<y.x; }
inline bool cmpy(node x,node y) {return x.y<y.y; }
inline int dist(int x,int y) {return abs(s[x].x-s[y].x)+abs(s[x].y-s[y].y); }
inline int maxf(int x,int rec) {return max(abs(s[x].x-L[rec]),abs(s[x].x-R[rec]))+max(abs(s[x].y-D[rec]),abs(s[x].y-U[rec])); }
inline int minf(int x,int rec) {return min(abs(s[x].x-L[rec]),abs(s[x].x-R[rec]))+min(abs(s[x].y-D[rec]),abs(s[x].y-U[rec])); }
inline void update(int x){
	L[x]=R[x]=s[x].x;
	D[x]=U[x]=s[x].y;
	if (lc[x]){
		L[x]=min(L[x],L[lc[x]]),R[x]=max(R[x],R[lc[x]]);
		D[x]=min(D[x],D[lc[x]]),U[x]=max(U[x],U[lc[x]]);
	}
	if (rc[x]){
		L[x]=min(L[x],L[rc[x]]),R[x]=max(R[x],R[rc[x]]);
		D[x]=min(D[x],D[rc[x]]),U[x]=max(U[x],U[rc[x]]);
	}
}
inline int build(int l,int r){
	if (l>r) return 0;
	if (l==r){
		update(l);
		return l;
	}
	double avx=0,avy=0,vax=0,vay=0;
	for (int i=l;i<=r;i++) avx+=s[i].x,avy+=s[i].y;
	double len=r-l+1;
	avx/=len,avy/=len;
	for (int i=l;i<=r;i++){
		vax+=(s[i].x-avx)*(s[i].x-avx);
		vay+=(s[i].y-avy)*(s[i].y-avy);
	}
	int mid=(l+r)>>1;
	if (vax>=vay) nth_element(s+l,s+mid,s+r+1,cmpx);
	else nth_element(s+l,s+mid,s+r+1,cmpy);
	lc[mid]=build(l,mid-1),rc[mid]=build(mid+1,r);
	update(mid);
	return mid;
}
inline void getmax(int l,int r,int x){
	if (l>r) return ;
	int mid=(l+r)>>1;
	if (mid!=x) maxd=max(maxd,dist(x,mid));
	int distl=maxf(x,lc[mid]),distr=maxf(x,rc[mid]);
	if (distl>maxd && distr>maxd){
		if (distl>=distr){
			getmax(l,mid-1,x);
			if (distr>maxd) getmax(mid+1,r,x);
		}else{
			getmax(mid+1,r,x);
			if (distl>maxd) getmax(l,mid-1,x);
		}
	}else{
		if (distl>maxd) getmax(l,mid-1,x);
		if (distr>maxd) getmax(mid+1,r,x);
	}
}
inline void getmin(int l,int r,int x){
	if (l>r) return ;
	int mid=(l+r)>>1;
	if (mid!=x) mind=min(mind,dist(x,mid));
	int distl=minf(x,lc[mid]),distr=minf(x,rc[mid]);
	if (distl<mind && distr<mind){
		if (distl<=distr){
			getmin(l,mid-1,x);
			if (distr<mind) getmin(mid+1,r,x);
		}else{
			getmin(mid+1,r,x);
			if (distl<mind) getmin(l,mid-1,x);
		}
	}else{
		if (distl<mind) getmin(l,mid-1,x);
		if (distr<mind) getmin(mid+1,r,x);
	}
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y);
	build(1,n);
	for (int i=1;i<=n;i++){
		maxd=0,mind=inf;
		getmax(1,n,i);
		getmin(1,n,i);
		ans=min(ans,maxd-mind);
	}
	printf("%d\n",ans);
	return 0;
}

求调，感激不尽！！