KDtree是一种分割$k$维数据空间的数据结构,主要应用于对关键字的搜索(范围搜索或最近邻搜索)。

KDtree是一棵二叉搜索树,如何确定左子树和右子树的划分,这是一个对提高效率有很大作用的操作。

以最近邻搜索(二维)为例,如果采用第一关键字,第二关键字的方式,可能点会在一块很密集的区间内分布。

而最近邻搜索一个很明显的减枝,就是利用分布较散的特性,来尽可能排除较多的远点。

显然,第一关键字,第二关键字的方式分布是窄条状的,并不满足这一条件。

给两个图自行体会一下。

维度交替18.PNG

第一关键字19.PNG

因此考虑采用维度交替的形式来进行分布,较真就用维度方差大的那个吧。

同时因为是一棵二叉搜索树,平衡状态,因而当前结点选择$\text{nth_element}$之后的$mid$结点。

上文就是建树的过程。

给定点询问最小值,对于当前左子树,如果这整个区间都不存在小过当前最小值的,就不用进行递归,对于右子树同理。

若存在,则优先访问较大区间,因为这样更优,有更多的可能性。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5,M=8555;
ll inf=1ll<<62;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n,k;
struct heap
{
    ll d[N];int len;
    void up(int j){for(int i=j>>1;j>1&&d[i]>d[j];j=i,i=j>>1)swap(d[i],d[j]);}
    void down(int i)
    {
        for(int j=i<<1;j<=len;i=j,j=i<<1)
        {
            if(j<len&&d[j+1]<d[j])++j;
            if(d[i]>d[j])swap(d[i],d[j]);
            else break;
        }
    }
    void push(ll x){d[++len]=x;up(len);}
    void pop(){d[1]=d[len--];down(1);}
    ll top(){return d[1];}
}q;
struct node{ll d[2];}a[N];
namespace KDTree
{
    int cnt,w;
    struct Seg{ll mx[2],mn[2];int ls,rs;}t[N];
    bool cmp(const node a,const node b){return a.d[w]<b.d[w];} 
    inline ll squ(ll x){return x*x;}
    inline ll dis(int p1,int p2){return squ(a[p1].d[0]-a[p2].d[0])+squ(a[p1].d[1]-a[p2].d[1]);}
    inline ll gdis(int p,node x)
    {
        ll tmp=0;
        tmp+=max(squ(t[p].mx[0]-x.d[0]),squ(t[p].mn[0]-x.d[0]));
        tmp+=max(squ(t[p].mx[1]-x.d[1]),squ(t[p].mn[1]-x.d[1]));
        return tmp;
    }
    inline void update(int x,int y)
    {
        t[x].mx[0]=max(t[x].mx[0],t[y].mx[0]);
        t[x].mx[1]=max(t[x].mx[1],t[y].mx[1]);
        t[x].mn[0]=min(t[x].mn[0],t[y].mn[0]);
        t[x].mn[1]=min(t[x].mn[1],t[y].mn[1]);
    }
    int build(int l,int r,int now)
    {
        w=now;int mid=l+r>>1;
        nth_element(a+l,a+mid,a+r+1,cmp);
        t[mid].mx[0]=t[mid].mn[0]=a[mid].d[0];
        t[mid].mx[1]=t[mid].mn[1]=a[mid].d[1];
        if(l!=mid)t[mid].ls=build(l,mid-1,now^1),update(mid,t[mid].ls);
        if(r!=mid)t[mid].rs=build(mid+1,r,now^1),update(mid,t[mid].rs);
        return mid;
    }
    void ask(int p,int id)
    {
        ll tmp=dis(p,id),dl=-inf,dr=-inf;
        if(t[p].ls)dl=gdis(t[p].ls,a[id]);
        if(t[p].rs)dr=gdis(t[p].rs,a[id]);
        if(q.top()<tmp)q.pop(),q.push(tmp);
        if(dl>=dr)
        {
            if(q.top()<dl&&t[p].ls)ask(t[p].ls,id);
            if(q.top()<dr&&t[p].rs)ask(t[p].rs,id);
        }
        else
        {
            if(q.top()<dr&&t[p].rs)ask(t[p].rs,id);
            if(q.top()<dl&&t[p].ls)ask(t[p].ls,id);
        }
    }
    void solve()
    {
        build(1,n,0);
        for(int i=1;i<=2*k;i++)q.push(0);
        for(int i=1;i<=n;i++)
            ask((1+n)>>1,i);
        qw(q.top());puts("");
    }
}
int main()
{
    //freopen("farthest1.in","r",stdin);
    qr(n),qr(k);
    for(int i=1;i<=n;i++)qr(a[i].d[0]),qr(a[i].d[1]);
    KDTree::solve();
    return 0;
}