KD-Tree

　　0.0找第k大……

　　裸KD-Tree……跟之前那道找最近的k个点大同小异

　　一开始理解错：第K大是第K远……不是第K近……（Tunix你个sb

　　感觉容易出错的是0号点= =边界情况需要仔细处理……根据题意而定的，比如这题就必须将0号点的距离设置成最近……比如-2……（因为我一开始向堆里加的占位点的距离是-1

1 /**************************************************************  2     Problem: 2626  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:12956 ms  7     Memory:4796 kb  8 ****************************************************************/  9   10 //BZOJ 2626 11 #include
      
        12 #include
       
         13 #include
        
          14 #include
         
           15 #include
          
            16 #include
           
             17 #define rep(i,n) for(int i=0;i
            
             =n;--i) 20 #define pb push_back 21 #define sqr(x) (x)*(x) 22 using namespace std; 23 typedef long long LL; 24 inline int getint(){ 25 int r=1,v=0; char ch=getchar(); 26 for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-1; 27 for(; isdigit(ch);ch=getchar()) v=v*10-'0'+ch; 28 return r*v; 29 } 30 const int N=100010,INF=1e9; 31 /*******************template********************/ 32 int n,m,root,D; 33 struct Poi{ 34 int d[2],mn[2],mx[2],l,r,num; 35 int& operator [] (int x){ return d[x];} 36 void read(){d[0]=getint();d[1]=getint();} 37 }t[N],now; 38 39 bool operator < (Poi a,Poi b) { return a[D]
             
              b.dis || (a.dis==b.dis && a.num
              
               >1) 50 void Push_up(int o){ 51 F(i,0,1){ 52 t[o].mn[i]=min(t[o].mn[i],min(t[L].mn[i],t[R].mn[i])); 53 t[o].mx[i]=max(t[o].mx[i],max(t[L].mx[i],t[R].mx[i])); 54 } 55 } 56 int build(int l,int r,int dir){ 57 D=dir; 58 nth_element(t+l,t+mid,t+r+1); 59 int o=mid; 60 F(i,0,1) t[o].mn[i]=t[o].mx[i]=t[o][i]; 61 if (l
               
                mid) R=build(mid+1,r,dir^1); 63 Push_up(o); 64 return o; 65 } 66 67 inline LL dis(Poi a,Poi b){ return (LL)sqr(a[0]-b[0])+(LL)sqr(a[1]-b[1]);} 68 inline LL getdis(int o){ 69 if (!o) return -2; 70 LL ans=0; 71 F(i,0,1) 72 ans+=max((LL)sqr(t[o].mx[i]-now[i]),(LL)sqr(t[o].mn[i]-now[i])); 73 return ans; 74 } 75 priority_queue
                
                 Q; 76 77 void query(int o){ 78 if (!o) return; 79 LL dl=getdis(L),dr=getdis(R),d0=dis(t[o],now); 80 if (d0>Q.top().dis || (d0==Q.top().dis && t[o].num
                 
                  dr){ 84 if (dl>=Q.top().dis) query(L); 85 if (dr>=Q.top().dis) query(R); 86 }else{ 87 if (dr>=Q.top().dis) query(R); 88 if (dl>=Q.top().dis) query(L); 89 } 90 } 91 92 int main(){ 93 #ifndef ONLINE_JUDGE 94 freopen("2626.in","r",stdin); 95 freopen("2626.out","w",stdout); 96 #endif 97 F(i,0,1) t[0].mn[i]=INF,t[0].mx[i]=-INF; 98 n=getint(); 99 F(i,1,n) t[i].read(),t[i].num=i;100 root=build(1,n,1);101 int T=getint();102 while(T--){103 now.read(); int k=getint();104 // printf("%d %d %d\n",now[0],now[1],k);105 while(!Q.empty()) Q.pop();106 F(i,1,k) Q.push(node(-1,0));107 query(root);108 printf("%d\n",Q.top().num);109 // printf("Q.size()=%d\n",Q.size());110 // F(i,1,k)111 // printf("%d -- %lld %lld\n",i,Q.top().dis,Q.top().num),Q.pop();112 // puts("");113 }114 return 0;115 }

View Code

2626: JZPFAR

Time Limit: 50 Sec Memory Limit: 128 MB

Submit: 665 Solved: 248

[][][]

Description

　　平面上有n个点。现在有m次询问，每次给定一个点(px, py)和一个整数k，输出n个点中离(px, py)的距离第k大的点的标号。如果有两个(或多个)点距离(px, py)相同，那么认为标号较小的点距离较大。

Input

　　第一行，一个整数n，表示点的个数。

　　下面n行，每行两个整数x_i, y_i，表示n个点的坐标。点的标号按照输入顺序，分别为1..n。

　　下面一行，一个整数m，表示询问个数。

　　下面m行，每行三个整数px_i, py_i, k_i，表示一个询问。

Output

　　m行，每行一个整数，表示相应的询问的答案。

Sample Input

0 0

0 1

0 2

1 1 2

0 0 3

0 1 1

Sample Output

数据规模和约定

　　50%的数据中，n个点的坐标在某范围内随机分布。

　　100%的数据中，n<=10^5, m<=10^4, 1<=k<=20，所有点(包括询问的点)的坐标满足绝对值<=10^9，n个点中任意两点坐标不同，m个询问的点的坐标在某范围内随机分布。

HINT

Source

[ ][ ][ ]

转载于:https://www.cnblogs.com/Tunix/p/4518205.html

你可能感兴趣的文章