平面上n个点，一个点的贡献是离他最远的点的距离减去离他最近的点的距离，求最小的贡献.n<=500000
kdtree模板题，学习一发。
#include<iostream> #include<cstdio> #include<algorithm> #define INF 2000000000 #define MN 500000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,now; inline int abs(int x){return x<0?-x:x;} struct P{ int d[2],mx[2],mn[2],l,r; int& operator[](int x){return d[x];} bool operator<(const P&x)const{return d[now]<x.d[now];} friend int dis(P x,P y){return abs(x.d[0]-y.d[0])+abs(x.d[1]-y.d[1]);} }t[MN+5]; struct KD_TREE{ P p[MN+5],T;int ans; void update(int x) { int l=p[x].l,r=p[x].r; for(int i=0;i<2;i++) { if(l) p[x].mn[i]=min(p[x].mn[i],p[l].mn[i]), p[x].mx[i]=max(p[x].mx[i],p[l].mx[i]); if(r) p[x].mn[i]=min(p[x].mn[i],p[r].mn[i]), p[x].mx[i]=max(p[x].mx[i],p[r].mx[i]); } } int getmn(P x) { int sum=0; for(int i=0;i<2;i++) { sum+=max(x.mn[i]-T[i],0); sum+=max(T[i]-x.mx[i],0); } return sum; } int getmx(P x) { int sum=0; for(int i=0;i<2;i++) sum+=max(abs(x.mn[i]-T[i]),abs(x.mx[i]-T[i])); return sum; } int build(int l,int r,int th) { int mid=l+r>>1;now=th; nth_element(t+l,t+mid,t+r+1); p[mid]=t[mid]; for(int i=0;i<2;i++) p[mid].mx[i]=p[mid].mn[i]=p[mid][i]; if(l<mid) p[mid].l=build(l,mid-1,th^1); if(mid<r) p[mid].r=build(mid+1,r,th^1); update(mid); return mid; } void querymn(int k) { int t=dis(p[k],T);if(t)ans=min(ans,t); int dl=INF,dr=INF; if(p[k].l) dl=getmn(p[p[k].l]); if(p[k].r) dr=getmn(p[p[k].r]); if(dl>dr) { if(dr<ans) querymn(p[k].r); if(dl<ans) querymn(p[k].l); } else { if(dl<ans) querymn(p[k].l); if(dr<ans) querymn(p[k].r); } } void querymx(int k) { ans=max(ans,dis(p[k],T)); int dl=-INF,dr=-INF; if(p[k].l) dl=getmx(p[p[k].l]); if(p[k].r) dr=getmx(p[p[k].r]); if(dl>dr) { if(dl>ans) querymx(p[k].l); if(dr>ans) querymx(p[k].r); } else { if(dr>ans) querymx(p[k].r); if(dl>ans) querymx(p[k].l); } } }kdtree; int rt,ans=INF; int main() { n=read(); for(int i=1;i<=n;i++) t[i][0]=read(),t[i][1]=read(); rt=kdtree.build(1,n,0); for(int i=1;i<=n;i++) { kdtree.T=t[i]; kdtree.ans=INF; kdtree.querymn(rt);int mn=kdtree.ans; kdtree.ans=-INF;kdtree.querymx(rt);int mx=kdtree.ans; ans=min(ans,mx-mn); } cout<<ans; return 0; }