BZOJ 4520: [Cqoi2016]K远点对

4520: [Cqoi2016]K远点对

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 638  Solved: 340
[Submit][Status][Discuss]

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

9

HINT

Source

[Submit][Status][Discuss]

建立KD-Tree，用堆维护当前找到的前K远点对。

枚举一个点，在树中遍历，尝试更新堆顶（较近的点对）。

注意用KD-Tree“估价函数”来剪枝，还有因为点对有重复，所以应当取出第2K远的点对。

 #include <bits/stdc++.h>

 const int siz = ;

 int n, m;

 struct node
 {
     int son[];
     int pos[];
     int maxi[];
     int mini[];
 }tr[siz];

 int cmpk;

 inline bool cmp(const node &a, const node &b)
 {
     if (a.pos[cmpk] != b.pos[cmpk])
         return a.pos[cmpk] < b.pos[cmpk];
     else
         return a.pos[cmpk^] < b.pos[cmpk^];
 }

 int build(int l, int r, int k)
 {
     int mid = (l + r) >> ; cmpk = k;

     std::nth_element(tr + l, tr + mid, tr + r + , cmp);

     if (l < mid)tr[mid].son[] = build(l, mid - , k ^ );
     if (r > mid)tr[mid].son[] = build(mid + , r, k ^ );

     tr[mid].maxi[] = tr[mid].mini[] = tr[mid].pos[];
     tr[mid].maxi[] = tr[mid].mini[] = tr[mid].pos[];

     for (int i = ; i < ; ++i)if (tr[mid].son[i])
         for (int j = ; j < ; ++j)
         {
             if (tr[mid].maxi[j] < tr[tr[mid].son[i]].maxi[j])
                 tr[mid].maxi[j] = tr[tr[mid].son[i]].maxi[j];
             if (tr[mid].mini[j] > tr[tr[mid].son[i]].mini[j])
                 tr[mid].mini[j] = tr[tr[mid].son[i]].mini[j];
         }

     return mid;
 }

 typedef long long lnt;

 const lnt inf = 2e18;

 std::priority_queue<
     lnt, std::vector<lnt>, std::greater<lnt>
 > heap;

 int qx, qy;

 inline lnt sqr(lnt x)
 {
     return x * x;
 }

 inline lnt calc(int t)
 {
     lnt dx = std::max(sqr(tr[t].mini[] - qx), sqr(tr[t].maxi[] - qx));
     lnt dy = std::max(sqr(tr[t].mini[] - qy), sqr(tr[t].maxi[] - qy));

     return dx + dy;
 }

 void query(int t)
 {
     lnt dis = sqr(tr[t].pos[] - qx) + sqr(tr[t].pos[] - qy);

     if (dis > heap.top())
     {
         heap.pop();
         heap.push(dis);
     }

     lnt dl = tr[t].son[] ? calc(tr[t].son[]) : -inf;
     lnt dr = tr[t].son[] ? calc(tr[t].son[]) : -inf;

     if (dl > dr)
     {
         if (dl > heap.top())query(tr[t].son[]);
         if (dr > heap.top())query(tr[t].son[]);
     }
     else
     {
         if (dr > heap.top())query(tr[t].son[]);
         if (dl > heap.top())query(tr[t].son[]);
     }
 }

 signed main(void)
 {
     scanf("%d%d", &n, &m);

     for (int i = ; i <= n; ++i)
         scanf("%d%d", &tr[i].pos[], &tr[i].pos[]);

     int root = build(, n, );

     for (int i = ; i <= *m; ++i)
         heap.push(0LL);

     for (int i = ; i <= n; ++i)
     {
         qx = tr[i].pos[];
         qy = tr[i].pos[];
         query(root);
     }

     printf("%lld\n", heap.top());
 }

@Author: YouSiki