BZOJ4520:[CQOI2016]K远点对(K-D Tree)-白红宇

BZOJ4520:[CQOI2016]K远点对(K-D Tree)

阅读量：6440 次

发布时间：2019-06-23

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

Description

已知平面内 N 个点的坐标，求欧氏距离下的第 K 远点对。

Input

输入文件第一行为用空格隔开的两个整数 N， K。接下来 N 行，每行两个整数 X,Y，表示一个点

的坐标。1 < = N < = 100000， 1 < = K < = 100， K < = N*(N−1)/2 ， 0 < = X, Y < 2^31。

Output

输出文件第一行为一个整数，表示第 K 远点对的距离的平方（一定是个整数）。

Sample Input

10 5

0 0

0 1

1 0

1 1

2 0

2 1

1 2

0 2

3 0

3 1

Sample Output

Solution

到现在为止只会写K-D Tree的板子题……

这次画了个图又理解了一下估价函数，感觉挺不错的

按照套路维护k远开个堆就好了，只不过由于这个题(x,y)和(y,x)算一对

需要开2*k的堆最后输出堆顶

Code

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define N (100000+1000) 9 #define INF 1e17 10 using namespace std; 11 12 struct P 13 { 14 long long dis,num; 15 bool operator < (const P &a) const{ return dis>a.dis;} 16 }po; 17 long long n,k,D,Root; 18 priority_queue
             q; 19 20 struct Node 21 { 22 long long d[2],Max[2],Min[2],lson,rson; 23 bool operator < (const Node &a) const { return d[D]
              
               r) return 0; 52 long long mid=(l+r)>>1; 53 D=opt; nth_element(p+l,p+mid,p+r+1); 54 Tree[mid]=p[mid]; 55 Tree[mid].lson=Build(opt^1,l,mid-1); 56 Tree[mid].rson=Build(opt^1,mid+1,r); 57 Update(mid); return mid; 58 } 59 long long Get_max(long long now) 60 { 61 long long ans=0; 62 for (int i=0; i<=1; ++i) 63 ans+=max(sqr(T.d[i]-Tree[now].Min[i]),sqr(T.d[i]-Tree[now].Max[i])); 64 return ans; 65 } 66 void Query(long long now) 67 { 68 long long ls=Tree[now].lson, rs=Tree[now].rson, lans=-INF, rans=-INF; 69 if (ls) lans=Get_max(ls); 70 if (rs) rans=Get_max(rs); 71 72 po.dis=sqr(T.d[0]-Tree[now].d[0])+sqr(T.d[1]-Tree[now].d[1]); po.num=now; 73 if (po.dis>q.top().dis) 74 q.pop(),q.push(po); 75 76 if (lans>rans) 77 { 78 if (lans>q.top().dis) Query(ls); 79 if (rans>q.top().dis) Query(rs); 80 } 81 else 82 { 83 if (rans>q.top().dis) Query(rs); 84 if (lans>q.top().dis) Query(ls); 85 } 86 } 87 }KDT; 88 89 int main() 90 { 91 scanf("%lld%lld",&n,&k); 92 for (int i=1; i<=n; ++i) 93 scanf("%lld%lld",&p[i].d[0],&p[i].d[1]); 94 Root=KDT.Build(0,1,n); 95 96 po.dis=-INF,po.num=0; 97 for (int i=1; i<=2*k; ++i) 98 q.push(po); 99 100 for (int i=1; i<=n; ++i)101 {102 T=KDT.Tree[i];103 KDT.Query(Root);104 }105 printf("%lld",q.top().dis);106 }