P4357 [CQOI2016] K 远点对 题解

· · 题解

这题标签错了吧？！

警钟敲烂：

如果你是奔着 KDT 算法正解来看这篇题解的话，请回炉重造，因为——KDT 根本就做不出来！！！

大致思路：

尽管本题出得十分得毒瘤具有挑战性，直接将像我这种幻想着用 KDT 做出满分的人给拒之门外了，但是为了这份纯真的热情，我还是来讲一下这道题 KDT 怎么做话说是啥时候出现了 hack 得数据。

这道题其实做法并不难，我们的目的是要找出第 k 远的点，则我们要维护一个有 k 个节点的小根堆，并在一开始将这些节点的点权默认为全部都是最小值（本题中设为 0 就可以了）。接着，我们这样在堆首的就是第 k 大值，这样我们只要枚举每个点，分别搜它们所对应的点，统计它们的贡献容易发现，因为是无序的点，不知道各个点的键值，就不知道它们的排列，只能都搜一遍，，因此这些点之间的距离会被计算 2 次，那我们只要把 k 变成 2 \times k 就好了。

代码如下（别直接复制，过不了）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 1;
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
priority_queue<int, vector<int>, greater<int> > q;
struct Point
{
    int x, y;
} point[N];
int n, k;
bool cmp1(Point a, Point b)
{
    return a.x < b.x;
}
bool cmp2(Point a, Point b)
{
    return a.y < b.y;
}
struct node
{
    int ch[2], L, R, D, U;
} t[N];
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
void push_up(int x)
{
    t[x].L = t[x].R = point[x].x;
    t[x].D = t[x].U = point[x].y;
    if (ls(x))
    {
        t[x].L = min(t[x].L, t[ls(x)].L);
        t[x].R = max(t[x].R, t[ls(x)].R);
        t[x].D = min(t[x].D, t[ls(x)].D);
        t[x].U = max(t[x].U, t[ls(x)].U);//懒人操作
    }
    if (rs(x))
    {
        t[x].L = min(t[x].L, t[rs(x)].L);
        t[x].R = max(t[x].R, t[rs(x)].R);
        t[x].D = min(t[x].D, t[rs(x)].D);
        t[x].U = max(t[x].U, t[rs(x)].U);
    }
}
#define pf(x) ((x) * (x))
int dist(int a, int b)
{
    return max(pf(point[a].x - t[b].L), pf(point[a].x - t[b].R)) + max(pf(point[a].y - t[b].D), pf(point[a].y - t[b].U));
}
int build(int l, int r)
{
    if (l > r)
    {
        return 0;
    }
    int mid = (l + r) >> 1;
    double av1 = 0, av2 = 0, va1 = 0, va2 = 0;
    for (int i = l; i <= r; i++)
    {
        av1 += point[i].x, av2 += point[i].y;
    }
    av1 /= (r - l + 1);
    av2 /= (r - l + 1);
    for (int i = l; i <= r; i++)
    {
        va1 += pf(av1 - point[i].x), va2 += pf(av2 - point[i].y);
    }
    if (va1 > va2)
    {
        nth_element(point + l, point + mid, point + r + 1, cmp1);
    }
    else
    {
        nth_element(point + l, point + mid, point + r + 1, cmp2);
    }
    ls(mid) = build(l, mid - 1);
    rs(mid) = build(mid + 1, r);
    push_up(mid);
    return mid;
}
void query(int l, int r, int x)
{
    if (l > r)
    {
        return;
    }
    int mid = (l + r) >> 1;
    int d = pf(point[mid].x - point[x].x) + pf(point[mid].y - point[x].y);
    if (d > q.top())
    {
        q.pop();
        q.push(d);
    }
    int distl = dist(x, ls(mid)), distr = dist(x, rs(mid));
    if (distl > q.top() && distr > q.top())
    {
        if (distl > distr)
        {
            query(l, mid - 1, x);
            if (distr > q.top())
            {
                query(mid + 1, r, x);
            }
        }
        else
        {
            query(mid + 1, r, x);
            if (distl > q.top())
            {
                query(l, mid - 1, x);
            }
        }
    }
    else
    {
        if (distl > q.top())
        {
            query(l, mid - 1, x);
        }
        if (distr > q.top())
        {
            query(mid + 1, r, x);
        }
    }
}
signed main()
{
    n = read();
    k = read();
    k *= 2;
    for (int i = 1; i <= k; i++)
    {
        q.push(0);
    }
    for (int i = 1; i <= n; i++)
    {
        point[i].x = read();
        point[i].y = read();
    }
    build(1, n);
    for (int i = 1; i <= n; i++)
    {
        query(1, n, i);
    }
    cout << q.top();
    return 0;
}