【kd-tree】bzoj1941 [Sdoi2010]Hide and Seek

枚举每个点，计算离他最近的和最远的点。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 500001
#define INF 2147483647
#define KD 2//ά¶ÈÊý
int qp[KD],disn,disx;
int n,root;
bool dn;
struct Node
{
    int minn[KD],maxx[KD],p[KD];
    int ch[2];
    void Init()
      {
        for(int i=0;i<KD;++i)
          minn[i]=maxx[i]=p[i];
      }
    int Disn()
      {
        int res=0;
        for(int i=0;i<KD;++i)
          {
            res+=max(0,minn[i]-qp[i]);
            res+=max(0,qp[i]-maxx[i]);
          }
        return res;
      }
    int Disx()
      {
        int res=0;
        for(int i=0;i<KD;++i)
          {
            res+=max(0,qp[i]-minn[i]);
            res+=max(0,maxx[i]-qp[i]);
          }
        return res;
      }
}T[N];
void Update(int rt)
{
    for(int i=0;i<2;++i)
      if(T[rt].ch[i])
        for(int j=0;j<KD;++j)
          {
            T[rt].minn[j]=min(T[rt].minn[j],T[T[rt].ch[i]].minn[j]);
            T[rt].maxx[j]=max(T[rt].maxx[j],T[T[rt].ch[i]].maxx[j]);
          }
}
int Abs(const int &x){return x<0 ? (-x) : x;}
int Dis(int a[],int b[]){return Abs(a[0]-b[0])+Abs(a[1]-b[1]);}
bool operator < (const Node &a,const Node &b){return a.p[dn]<b.p[dn];}
int Buildtree(int l=1,int r=n,bool d=0)
{
    dn=d;
    int m=(l+r>>1);
    nth_element(T+l,T+m,T+r+1);
    T[m].Init();
    if(l!=m) T[m].ch[0]=Buildtree(l,m-1,d^1);
    if(m!=r) T[m].ch[1]=Buildtree(m+1,r,d^1);
    Update(m);
    return m;
}
int I=1;
void Queryn(int rt=root)
{
    if(rt!=I)
      disn=min(disn,Dis(T[rt].p,qp));
    int dd[2];
    for(int i=0;i<2;i++)
      if(T[rt].ch[i])
        dd[i]=T[T[rt].ch[i]].Disn();
      else dd[i]=INF;
    bool f=(dd[0]<=dd[1]);
    if(dd[!f]<disn && T[rt].ch[!f]) Queryn(T[rt].ch[!f]);
    if(dd[f]<disn && T[rt].ch[f]) Queryn(T[rt].ch[f]);
}
void Queryx(int rt=root)
{
    if(rt!=I)
      disx=max(disx,Dis(T[rt].p,qp));
    int dd[2];
    for(int i=0;i<2;i++)
      if(T[rt].ch[i])
        dd[i]=T[T[rt].ch[i]].Disx();
      else dd[i]=-INF;
    bool f=(dd[0]>=dd[1]);
    if(dd[!f]>disx && T[rt].ch[!f]) Queryx(T[rt].ch[!f]);
    if(dd[f]>disx && T[rt].ch[f]) Queryx(T[rt].ch[f]);
}
int ans=INF;
int main()
{
//  freopen("bzoj1941.in","r",stdin);
//  freopen("bzoj2716.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
      scanf("%d%d",&T[i].p[0],&T[i].p[1]);
    root=(1+n>>1);
    Buildtree();
    for(;I<=n;++I)
      {
        disn=INF;
        disx=0;
        qp[0]=T[I].p[0];
        qp[1]=T[I].p[1];
        Queryn();
        Queryx();
        ans=min(ans,disx-disn);
      }
    printf("%d
",ans);
    return 0;
}