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

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<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<queue>
  7 #include<algorithm>
  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<P>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]<a.d[D];}
 24 }p[N],T;
 25 
 26 struct KDT
 27 {
 28     Node Tree[N];
 29     long long sqr(long long x){return x*x;}
 30     
 31     void Update(long long now)
 32     {
 33         for (int i=0; i<=1; ++i)
 34         {
 35             long long ls=Tree[now].lson, rs=Tree[now].rson;
 36             Tree[now].Max[i]=Tree[now].Min[i]=Tree[now].d[i];
 37             if (ls)
 38             {
 39                 Tree[now].Max[i]=max(Tree[now].Max[i],Tree[ls].Max[i]);
 40                 Tree[now].Min[i]=min(Tree[now].Min[i],Tree[ls].Min[i]);
 41             }
 42             if (rs)
 43             {
 44                 Tree[now].Max[i]=max(Tree[now].Max[i],Tree[rs].Max[i]);
 45                 Tree[now].Min[i]=min(Tree[now].Min[i],Tree[rs].Min[i]);
 46             }
 47         }
 48     }
 49     long long Build(long long opt,long long l,long long r)
 50     {
 51         if (l>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 }