【kd-tree】CDOJ - 1170 - 红与蓝

kd-tree模板题，对红点建立kd-tree，用每个蓝点查询，更新最小值即可。

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define N 100010

#define EPS 0.00000001

#define INF 1000000000000000007.0

#define KD 2

int qp[KD];

double disn;

int n,root;

bool dn;

double sqr(int x)

{

	return (double)x*(double)x;

}

int Abs(int x)

{

	return x<0 ? (-x) : x;

}

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];

      }

    bool CheckIn()

      {

      	for(int i=0;i<KD;++i)

      	  if(!(minn[i]<=qp[i] && qp[i]<=maxx[i]))

      	    return 0;

      	return 1;

      }

    int Dis()

      {

      	if(CheckIn())

      	  return 0;

        int res=2147483647;

        res=min(res,Abs(minn[0]-qp[0]));

        res=min(res,Abs(maxx[0]-qp[0]));

        res=min(res,Abs(minn[1]-qp[1]));

        res=min(res,Abs(maxx[1]-qp[1]));

        return res;

      }

}T[N<<1];

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]);

          }

}

bool operator < (const Node &a,const Node &b)

{

    return a.p[dn]!=b.p[dn] ? a.p[dn]<b.p[dn] : a.p[dn^1]<b.p[dn^1];

}

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;

}

double Dis(int a[],int b[])

{

    return sqrt(sqr(a[0]-b[0])+sqr(a[1]-b[1]));

}

void Query(int rt=root)

{

    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]].Dis();

      else dd[i]=2147483647;

    bool f=(dd[0]<=dd[1]);

    if((double)dd[!f]-disn<(-EPS)) Query(T[rt].ch[!f]);

    if((double)dd[f]-disn<(-EPS)) Query(T[rt].ch[f]);

}

int main()

{

//	freopen("k.in","r",stdin);

//	freopen("k.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();

    disn=INF;

    for(int i=1;i<=n;++i)

      {

        scanf("%d%d",&qp[0],&qp[1]);

        Query();

      }

    printf("%.3lf\n",disn);

    return 0;

}