K远点对（K-D Tree）

K远点对

K-D Tree 真是优雅的暴力！开局建棵树，剪枝刷题数！

题意：
给定二维平面上的 $N$N个点，求第 $K$K远的无序点对。

思路：

1. 别问我为什么想到用K-D Tree的，因为是看了题解的。
2. 本题没有插入、删除等高级操作，仅仅建树和查询，代码简洁。
3. 进入正题：考虑暴力，暴力遍历对于每个点而言能形成的所有点对，显然复杂度为 $O\left(n^2\right)$O(n2)，不可行，接下来考虑剪枝。
4. 首先， $K=min(100,\frac{n\ast (n+1)}{2})$K=min(100,2n∗(n+1)​)，所以先在小顶堆中插入 $2\ast K$2∗K个 $0$0，在后续暴力搜索前 $2\ast K$2∗K大点对的过程中逐渐把它们 $pop$pop掉。
5. 对这 $N$N个点的每个点而言，都从K-D Tree的根节点往下遍历，每到一个节点，先计算当前节点与这个点的距离，并更新小顶堆，然后进入到剪枝的关键步骤。
6. 我们考虑每个节点的左右儿子，分别利用左右儿子的每个维度最大最小边界来计算可能的最远点，若当前子空间最远的点都无法对小顶堆进行更新，则不需要进入这个空间了！
7. 另一点剪枝：先遍历左右子空间中最远可能点更远的子空间，这样也许就不用再遍历另外一个空间啦。
8. 复杂度的话。。。还不会算，据说是 $O\left(n^{\frac{3}{2}}\right)$O(n23​)。

代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int N, K, rt, tot, Dim;
int ls[maxn], rs[maxn];
ll mi[maxn][2], mx[maxn][2];
priority_queue<ll,vector<ll>,greater<ll> > q;

struct P{
    ll x[2];
    friend bool operator < (const P &a, const P &b) {
        return a.x[Dim]<b.x[Dim];
    }
    friend inline ll cal(const P &a, const P &b) {
        return (a.x[0]-b.x[0])*(a.x[0]-b.x[0])+(a.x[1]-b.x[1])*(a.x[1]-b.x[1]);
    }
    inline ll cal(const ll mi[2], const ll mx[2]) {
        ll d1=max(abs(x[0]-mi[0]),abs(x[0]-mx[0]));
        ll d2=max(abs(x[1]-mi[1]),abs(x[1]-mx[1]));
        return d1*d1+d2*d2;
    }
}p[maxn], tmp[maxn];

inline void Min(ll &a, ll b) { if(a>b) a=b; }
inline void Max(ll &a, ll b) { if(a<b) a=b; }

void push_up(int now) {
    for(int i=0; i<2; ++i) {
        mi[now][i]=mx[now][i]=p[now].x[i];
        if(ls[now]) Min(mi[now][i],mi[ls[now]][i]), Max(mx[now][i],mx[ls[now]][i]);
        if(rs[now]) Min(mi[now][i],mi[rs[now]][i]), Max(mx[now][i],mx[rs[now]][i]);
    }
}

void build(int l, int r, int dim, int &now) {
    if(l>r) return;
    now=++tot;
    int m=(l+r)/2;
    Dim=dim; nth_element(tmp+l,tmp+m,tmp+r+1); p[now]=tmp[m];
    build(l,m-1,dim^1,ls[now]); build(m+1,r,dim^1,rs[now]);
    push_up(now);
}

void query(P &a, int now) {
    ll t=cal(a,p[now]), lt=0, rt=0;
    if(t>q.top()) q.pop(), q.push(t);
    if(ls[now]) lt=a.cal(mi[ls[now]],mx[ls[now]]);
    if(rs[now]) rt=a.cal(mi[rs[now]],mx[rs[now]]);
    if(lt>rt) {
        if(lt>q.top()) query(a,ls[now]);
        if(rt>q.top()) query(a,rs[now]);
    }
    else {
        if(rt>q.top()) query(a,rs[now]);
        if(lt>q.top()) query(a,ls[now]);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N>>K;
    for(int i=1; i<=N; ++i) cin>>tmp[i].x[0]>>tmp[i].x[1];
    build(1,N,0,rt);
    for(int i=1; i<=2*K; ++i) q.push(0);
    for(int i=1; i<=N; ++i) query(tmp[i],rt);
    cout<<q.top()<<endl;
}