【堆】【kd-tree】bzoj2626 JZPFAR-白红宇

【堆】【kd-tree】bzoj2626 JZPFAR

阅读量：5967 次

发布时间：2019-06-19

本文共 1117 字，大约阅读时间需要 3 分钟。

用堆记录答案。看看当前点是否比堆顶更优。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef double db;#define N 100001#define EPS 0.0000001#define INF 999999999999999999.0#define KD 2//Î¬¶ÈÊýint qp[KD];int n,root,kd=2,K;int dn;struct Ans{    int p[KD],id;    db d;    Ans(){}    Ans(int _p[],int _id,db _d){memcpy(p,_p,sizeof(p)); id=_id; d=_d;}};bool operator < (const Ans &a,const Ans &b){return fabs(a.d-b.d)>=EPS ? a.d>b.d : a.id
          
           
            Heap;db sqr(const int &x){return (db)x*(db)x;}struct Node{ int minn[KD],maxx[KD],p[KD],id; int ch[2]; void Init() { for(int i=0;i
            
             >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)%kd); if(m!=r) T[m].ch[1]=Buildtree(m+1,r,(d+1)%kd); Update(m); return m;}void Query(int rt=root){ db t=Dis(T[rt].p,qp); if(Heap.size()
             
              =dd[1]); if((dd[!f]-Heap.top().d>EPS || Heap.size()
              
               EPS || Heap.size()
               
                >1); scanf("%d",&q); for(;q;--q) { while(!Heap.empty()) Heap.pop(); for(int i=0;i