洛谷P4357 [CQOI2016]K 远点对 题解

题目链接：P4357 [CQOI2016]K 远点对

题意：给定平面内 \(n\) 个点的坐标，求欧几里德距离第 \(k\) 远的点对

本题的正解应该是旋转卡壳、分治等算法，不会

而kd-tree上搜索在本题中相当于搜索+天然剪枝

因此假装这就是个kd-tree的模板题

为什么使用方差呢？因为方差很好描述了数据的离散程度

每次选择方差较大的进行划分，是因为选择较小的很可能导致另一维的方差过高

因此这样就很难保证树高

对于本题中的 \(k\) 大值怎么去维护呢？

我们可以弄一个有 \(k\) 个结点的小根堆，这些结点默认为一个极小值（本题中设为 \(0\) 就可以了）

这样在堆首的就是第 \(k\) 大值了

这样我们只要枚举每个点，分别搜它们所对应的点，统计它们的贡献

容易发现，因为是无序的点，因此这些点之间的距离会被计算 \(2\) 次，那我们只要把 \(k\) 变成 \(2k\) 就好了

时间复杂度 比较玄学，可以分析的是建树 \(O(n\log n)\)

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define N (int)(1e5+5)
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('\n');}
    if(k>9)write(k/10);
    pc(k%10+'0');
}
priority_queue< int,vector<int>,greater<int> >q;
struct Point
{
    int x,y;
}s[N];
int n,k;
namespace KDT
{
    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=s[x].x;
        t[x].D=t[x].U=s[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 sq(x) ((x)*(x))
    int dist(int a,int b)
    {
        return max(sq(s[a].x-t[b].L),sq(s[a].x-t[b].R))
        +max(sq(s[a].y-t[b].D),sq(s[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+=s[i].x,av2+=s[i].y;
        av1/=(r-l+1);
        av2/=(r-l+1);
        for(int i=l; i<=r; i++)
            va1+=sq(av1-s[i].x),va2+=sq(av2-s[i].y);
        if(va1>va2)
            nth_element(s+l,s+mid,s+r+1,cmp1);
        else nth_element(s+l,s+mid,s+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=sq(s[mid].x-s[x].x)+sq(s[mid].y-s[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()
{
    using namespace KDT;
    read(n);read(k);
    k*=2; // 无序点对，每个有序点对会被计算两次
    for(int i=1; i<=k; i++) q.push(0);
    for(int i=1; i<=n; i++)
        read(s[i].x),read(s[i].y);
    build(1,n);
    for(int i=1; i<=n; i++)
        query(1,n,i);
    write(q.top());pc('\n');
    return 0;
}