KD-Tree一系列模板题

时间：2021-09-12 09:25:11

刚学kd-tree，具体的操作网上都有，我就不赘述了。今天暂时只刷了一些曼哈顿距离的题目……都水水的，核心思想是记录出每个超平面（这个词好喜感=v=）的边缘坐标，利用估价函数判断询问点到两边超平面最近的距离是什么，然后先去那个超平面搜索，以达到启发式搜索和剪枝的目的。
KD-Tree一系列模板题
具体来说，若要询问绿色的点，它到左边超平面最近的距离就是绿线的距离，我们就把这个距离作为估价函数就好了。（到右边的我没有画出来，但是估价函数会计算出0）

BZOJ2716 & 2648

双倍经验题+模板题，都是裸的询问离某个点曼哈顿距离最近的点是哪个点，直接用我上面说的算法就好了，询问的时候启发式搜索。

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define maxn 500000+5
#define INF 0x3f3f3f3f

using namespace std;

int n,m,dim,ans,root,cnt;

struct Point{
    int x[2];
    Point(int a=0,int b=0){ x[0]=a; x[1]=b; }
    inline int& operator [](int i){ return x[i]; }
    inline bool operator <(const Point &T)const{ return x[dim]<T.x[dim]; }
}p[maxn];

struct KD_Tree{
    int l,r;
    int mx[2],mi[2]; //记录边界，使用估价函数剪枝，需要维护一个子树的平面空间范围
    Point t;
}tr[maxn<<1];

#define mid ((l+r)>>1)

inline int in(){
    int x=0,f=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(; isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

inline void Update_mx(int &x,int y){ if(y>x) x=y; }

inline void Update_mi(int &x,int y){ if(y<x) x=y; }

inline int dis(Point a,Point b){
    return abs(a[0]-b[0])+abs(a[1]-b[1]);
}

int calc(int k,Point x){
    int res=0;
    for(int i=0;i<2;i++){
        res+=max(0,tr[k].mi[i]-x[i]);
        res+=max(0,x[i]-tr[k].mx[i]);
    }
    return res;
}

void Update(int k){
    for(int i=0;i<2;i++){
        if(tr[k].l) Update_mx(tr[k].mx[i],tr[tr[k].l].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].l].mi[i]);
        if(tr[k].r) Update_mx(tr[k].mx[i],tr[tr[k].r].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].r].mi[i]);
    }
}

void Build(int &k,int l,int r,int d){
    dim=d; k=++cnt;
    nth_element(p+l,p+mid,p+r+1);
    tr[k].t=p[mid];
    for(int i=0;i<2;i++)
        tr[k].mx[i]=tr[k].mi[i]=p[mid][i];
    if(l<mid) Build(tr[k].l,l,mid-1,d^1);
    if(mid<r) Build(tr[k].r,mid+1,r,d^1);
    Update(k);
}

void Insert(int &k,Point pt,int d){
    if(!k){
        k=++cnt;
        for(int i=0;i<2;i++) tr[k].mx[i]=tr[k].mi[i]=pt[i];
        tr[k].t=pt; return;
    }
    dim=d;
    if(pt<tr[k].t) Insert(tr[k].l,pt,d^1);
    else Insert(tr[k].r,pt,d^1);
    Update(k);
}

void Query(int k,Point pt,int d){
    if(!k) return;
    ans=min(ans,dis(pt,tr[k].t));
    int lv=INF,rv=INF;
    if(tr[k].l) lv=calc(tr[k].l,pt);
    if(tr[k].r) rv=calc(tr[k].r,pt);
    if(lv<rv){
        if(lv<ans) Query(tr[k].l,pt,d^1);
        if(rv<ans) Query(tr[k].r,pt,d^1);
    }
    else{
        if(rv<ans) Query(tr[k].r,pt,d^1);
        if(lv<ans) Query(tr[k].l,pt,d^1);       
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("2648.in","r",stdin);
    freopen("2648.out","w",stdout);
#endif
    n=in(); m=in();
    for(int i=1;i<=n;i++){
        p[i][0]=in(); p[i][1]=in();    
    }
    Build(root,1,n,0);
    for(int opt,x,y,i=1;i<=m;i++){
        opt=in(); x=in(); y=in();
        if(opt==1) Insert(root,Point(x,y),0);       
        else{
            ans=INF;
            Query(root,Point(x,y),0);
            printf("%d\n",ans);
        }
    }
    return 0;
}

BZOJ1941

跟上面一样是模板题……只需要枚举每个点进行询问，更新最近最远点之间的差就好了。
然而这题要还询问最远点，怎么办呢？
仿照最小值的估价函数也造一个差不多的就好了呗……意义是离某个超平面可能达到的最远距离。
（我会告诉你我偷懒从上面复制代码改了改吗？）

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define maxn 500000+5
#define INF 0x3f3f3f3f

using namespace std;

int n,m,dim,ans,ans1,ans2,root,cnt;

struct Point{
    int x[2];
    Point(int a=0,int b=0){ x[0]=a; x[1]=b; }
    inline int& operator [](int i){ return x[i]; }
    inline bool operator <(const Point &T)const{ return x[dim]<T.x[dim]; }
}p[maxn];

struct KD_Tree{
    int l,r;
    int mx[2],mi[2]; 
    Point t;
}tr[maxn<<1];

#define mid ((l+r)>>1)

inline int in(){
    int x=0,f=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(; isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

inline void Update_mx(int &x,int y){ if(y>x) x=y; }

inline void Update_mi(int &x,int y){ if(y<x) x=y; }

inline int dis(Point a,Point b){
    return abs(a[0]-b[0])+abs(a[1]-b[1]);
}

int calc1(int k,Point x){
    int res=0;
    for(int i=0;i<2;i++){
        res+=max(0,tr[k].mi[i]-x[i]);
        res+=max(0,x[i]-tr[k].mx[i]);
    }
    return res;
}

int calc2(int k,Point x){
    int res=0;
    for(int i=0;i<2;i++)
        res+=max(abs(x[i]-tr[k].mx[i]),abs(tr[k].mi[i]-x[i]));
    return res;
}

void Update(int k){
    for(int i=0;i<2;i++){
        if(tr[k].l) Update_mx(tr[k].mx[i],tr[tr[k].l].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].l].mi[i]);
        if(tr[k].r) Update_mx(tr[k].mx[i],tr[tr[k].r].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].r].mi[i]);
    }
}

void Build(int &k,int l,int r,int d){
    dim=d; k=++cnt;
    nth_element(p+l,p+mid,p+r+1);
    tr[k].t=p[mid];
    for(int i=0;i<2;i++)
        tr[k].mx[i]=tr[k].mi[i]=p[mid][i];
    if(l<mid) Build(tr[k].l,l,mid-1,d^1);
    if(mid<r) Build(tr[k].r,mid+1,r,d^1);
    Update(k);
}

void Insert(int &k,Point pt,int d){
    if(!k){
        k=++cnt;
        for(int i=0;i<2;i++) tr[k].mx[i]=tr[k].mi[i]=pt[i];
        tr[k].t=pt; return;
    }
    dim=d;
    if(pt<tr[k].t) Insert(tr[k].l,pt,d^1);
    else Insert(tr[k].r,pt,d^1);
    Update(k);
}

void Query_mi(int k,Point pt,int d){
    if(!k) return;
    if(dis(pt,tr[k].t)!=0) ans1=min(ans1,dis(pt,tr[k].t));
    int lv=INF,rv=INF;
    if(tr[k].l) lv=calc1(tr[k].l,pt);
    if(tr[k].r) rv=calc1(tr[k].r,pt);
    if(lv<rv){
        if(lv<ans1) Query_mi(tr[k].l,pt,d^1);
        if(rv<ans1) Query_mi(tr[k].r,pt,d^1);
    }
    else{
        if(rv<ans1) Query_mi(tr[k].r,pt,d^1);
        if(lv<ans1) Query_mi(tr[k].l,pt,d^1);       
    }
}

void Query_mx(int k,Point pt,int d){
    if(!k) return;
    ans2=max(ans2,dis(pt,tr[k].t));
    int lv=-INF,rv=-INF;
    if(tr[k].l) lv=calc2(tr[k].l,pt);
    if(tr[k].r) rv=calc2(tr[k].r,pt);
    if(lv>rv){
        if(lv>ans2) Query_mx(tr[k].l,pt,d^1);
        if(rv>ans2) Query_mx(tr[k].r,pt,d^1);
    }
    else{
        if(rv>ans2) Query_mx(tr[k].r,pt,d^1);
        if(lv>ans2) Query_mx(tr[k].l,pt,d^1);       
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("1941.in","r",stdin);
    freopen("1941.out","w",stdout);
#endif
    n=in(); 
    for(int i=1;i<=n;i++){
        p[i][0]=in(); p[i][1]=in();    
    }
    Build(root,1,n,0); ans=INF;
    for(int i=1;i<=n;i++){
        ans1=INF; ans2=-INF;
        Query_mi(root,p[i],0); Query_mx(root,p[i],0);
        ans=min(ans,ans2-ans1);
    }
    printf("%d",ans);
    return 0;
}

刷了几天……感觉KD-Tree就是个暴力+优化= =

BZOJ4066

这个题有插入操作，插入太多次以后KD树没办法保持平衡……于是到一定的次数就重构一次树好了……

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define maxn 200000+5

using namespace std;

int dim,n,cnt,root,ans,pos;

struct Point{
    int x[2],val;
    Point(int a=0,int b=0,int c=0){ x[0]=a; x[1]=b; val=c; }
    inline int operator [] (int i){ return x[i]; }
    inline bool operator < (const Point &T)const{ return x[dim]<T.x[dim]; }
}p[maxn];

struct KD_Tree{
    int l,r,sum;
    int mx[2],mi[2];
    Point t;
}tr[maxn];

inline int in(){
    int x=0,f=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(; isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

inline void Update_mx(int &x,int y){ if(y>x) x=y; }

inline void Update_mi(int &x,int y){ if(y<x) x=y; }

void Update(int k){
    for(int i=0;i<2;i++){
        if(tr[k].l) Update_mx(tr[k].mx[i],tr[tr[k].l].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].l].mi[i]);
        if(tr[k].r) Update_mx(tr[k].mx[i],tr[tr[k].r].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].r].mi[i]);
    }
    tr[k].sum=tr[tr[k].l].sum+tr[tr[k].r].sum+tr[k].t.val;
}

void Insert(int &k,Point pt,int d){
    if(!k){
        k=++cnt; tr[k].t=pt; tr[k].sum=pt.val;
        for(int i=0;i<2;i++) tr[k].mx[i]=tr[k].mi[i]=pt[i];
        return;
    }
    if(pt[0]==tr[k].t[0] && pt[1]==tr[k].t[1]){ tr[k].sum+=pt.val; tr[k].t.val+=pt.val; return; }
    dim=d;
    if(pt<tr[k].t) Insert(tr[k].l,pt,d^1);
    else Insert(tr[k].r,pt,d^1);
    Update(k);
}

inline bool cross(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
    if(x1<x4 || x2>x3 || y2<y3 || y1>y4) return false;
    return true;
}

inline bool cover(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){ //1-2 cover 3-4
    if(y1<=y3 && y2>=y4 && x1>=x3 && x2<=x4) return true;
    return false;
}

int Query(int k,int x1,int y1,int x2,int y2){
    if(cover(x1,y1,x2,y2,tr[k].mx[0],tr[k].mi[1],tr[k].mi[0],tr[k].mx[1])) return tr[k].sum;
    int tmp=0,l=tr[k].l,r=tr[k].r;
    if(tr[k].t[0]<=x1 && tr[k].t[0]>=x2 && tr[k].t[1]>=y1 && tr[k].t[1]<=y2) tmp+=tr[k].t.val;
    if(l && cross(x1,y1,x2,y2,tr[l].mx[0],tr[l].mi[1],tr[l].mi[0],tr[l].mx[1])) tmp+=Query(l,x1,y1,x2,y2);
    if(r && cross(x1,y1,x2,y2,tr[r].mx[0],tr[r].mi[1],tr[r].mi[0],tr[r].mx[1])) tmp+=Query(r,x1,y1,x2,y2);
    return tmp;
}

#define mid ((l+r)>>1)

void Rebuild(int &k,int l,int r,int d){
    dim=d; k=++cnt;
    nth_element(p+l,p+mid,p+r+1);
    tr[k].t=p[mid];
    for(int i=0;i<2;i++) tr[k].mx[i]=tr[k].mi[i]=p[mid][i];
    if(l<mid) Rebuild(tr[k].l,l,mid-1,d^1);
    else tr[k].l=0;
    if(r>mid) Rebuild(tr[k].r,mid+1,r,d^1);
    else tr[k].r=0;
    Update(k);
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("4066.in","r",stdin);
    freopen("4066.out","w",stdout);
#endif
    n=in(); int flag=10000;
    for(int opt;(opt=in())!=3;){
        if(opt==1){
            int x,y,c;
            x=in()^ans; y=in()^ans; c=in()^ans;
            Insert(root,Point(x,y,c),0);
            if(cnt==flag){
                for(int i=1;i<=cnt;i++) p[i]=tr[i].t,tr[i].sum=0;               
                int tmp=cnt; cnt=0; flag+=10000;
                Rebuild(root,1,tmp,0);
            }
        }
        else{
            int x1,y1,x2,y2;
            x1=in()^ans; y1=in()^ans; x2=in()^ans; y2=in()^ans;
            printf("%d\n",ans=Query(root,x2,y1,x1,y2));
        }
    }
    return 0;
}

BZOJ2850

计算一个矩形内的贡献和计算一个半平面的贡献都差不多……

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define maxn 50000+5

using namespace std;

typedef long long LL;

int n,m,dim,root,cnt;

struct Point{
    int x[2],h;
    Point(int a=0,int b=0,int c=0){ x[0]=a; x[1]=b; h=c; }
    inline int operator [] (int i){ return x[i]; }
    inline bool operator < (const Point &T)const{ return x[dim]<T.x[dim]; } 
}p[maxn];

struct KD_Tree{
    int l,r; LL sum;
    int mx[2],mi[2];
    Point t;
}tr[maxn];

inline int in(){
    int x=0,f=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(; isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

#define mid ((l+r)>>1)

inline void Update_mx(int &x,int y){ if(y>x) x=y; }

inline void Update_mi(int &x,int y){ if(y<x) x=y; }


void Update(int k){
    for(int i=0;i<2;i++){
        if(tr[k].l) Update_mx(tr[k].mx[i],tr[tr[k].l].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].l].mi[i]);
        if(tr[k].r) Update_mx(tr[k].mx[i],tr[tr[k].r].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].r].mi[i]);
    }
    tr[k].sum=tr[tr[k].l].sum+tr[tr[k].r].sum+tr[k].t.h;
}

void Build(int &k,int l,int r,int d){
    if(l>r){ k=0; return; }
    dim=d; k=++cnt;
    nth_element(p+l,p+mid,p+r+1);
    tr[k].t=p[mid]; 
    for(int i=0;i<2;i++) tr[k].mi[i]=tr[k].mx[i]=p[mid][i];
    Build(tr[k].l,l,mid-1,d^1);
    Build(tr[k].r,mid+1,r,d^1);
    Update(k);
}

inline bool cover(int x,int y,int a,int b,int c){
    return a*x+b*y<c;
}

int calc(int k,int a,int b,int c){
    int tmp=0;
    tmp+=cover(tr[k].mx[0],tr[k].mx[1],a,b,c);
    tmp+=cover(tr[k].mx[0],tr[k].mi[1],a,b,c);
    tmp+=cover(tr[k].mi[0],tr[k].mx[1],a,b,c);
    tmp+=cover(tr[k].mi[0],tr[k].mi[1],a,b,c);
    return tmp;
}

LL Query(int k,int a,int b,int c){
    if(calc(k,a,b,c)==4) return tr[k].sum; 
    LL tmp=0;
    if(tr[k].l && calc(tr[k].l,a,b,c)) tmp+=Query(tr[k].l,a,b,c);
    if(tr[k].r && calc(tr[k].r,a,b,c)) tmp+=Query(tr[k].r,a,b,c);
    if(cover(tr[k].t[0],tr[k].t[1],a,b,c)) tmp+=tr[k].t.h;
    return tmp;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("2850.in","r",stdin);
    freopen("2850.out","w",stdout);
#endif
    n=in(); m=in();
    for(int i=1;i<=n;i++){
        p[i].x[0]=in(); p[i].x[1]=in(); p[i].h=in();
    }
    Build(root,1,n,0);
    for(int a,b,c,i=1;i<=m;i++){
        a=in(); b=in(); c=in();
        printf("%lld\n",Query(root,a,b,c));
    }
    return 0;
}

BZOJ4154

稍微分析一下，发现这个点的染色范围在dfs序的一个区间内，在深度的一个区间内，把这个看成横纵坐标就可以转化成一个矩形内的点的涂色了……直接KD-Tree+Tag下传

#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<algorithm>

#define maxn 100000+5
#define mod 1000000007

using namespace std;

int n,c,q,dim,cnt,root,ans,ind,timer;

struct Point{
    int x[2],col,id;
    Point(int a=0,int b=0,int co=0,int d=0){ x[0]=a; x[1]=b; col=co; id=d; }
    inline int operator [] (int i){ return x[i]; }
    inline bool operator < (const Point &T)const{
        if(x[dim]==T.x[dim]) return x[dim^1]<T.x[dim^1];
        return x[dim]<T.x[dim];
    }
}p[maxn];

struct KD_Tree{
    int l,r,tag;
    int mx[2],mi[2];
    Point t;    
}tr[maxn];

struct Edge{
    int u,v,nxt;
}e[maxn<<1];

int head[maxn],dfn[maxn],last[maxn],dep[maxn],pos[maxn];

inline int in(){
    int x=0,f=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
    for(; isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}

inline void addedge(int x,int y){
    e[ind]=(Edge){x,y,head[x]},head[x]=ind++;
}

inline bool cmp(const Point &s,const Point &b){
    return s.id<b.id;
}

void dfs(int x){
    dfn[x]=++timer;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        dep[e[i].v]=dep[x]+1;               
        dfs(e[i].v);            
    }
    last[x]=timer;
}

#define mid ((l+r)>>1)

inline void Update_mx(int &x,int y){ if(x<y) x=y; }

inline void Update_mi(int &x,int y){ if(x>y) x=y; }

void Update(int k){
    for(int i=0;i<2;i++){
        if(tr[k].l) Update_mx(tr[k].mx[i],tr[tr[k].l].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].l].mi[i]);
        if(tr[k].r) Update_mx(tr[k].mx[i],tr[tr[k].r].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].r].mi[i]);
    }
}

void Build(int &k,int l,int r,int d){
    if(l>r){ k=0; return; }
    dim=d; k=++cnt;
    nth_element(p+l,p+mid,p+r+1);
    tr[k].t=p[mid]; tr[k].tag=-1; pos[p[mid].id]=k;
    for(int i=0;i<2;i++) tr[k].mx[i]=tr[k].mi[i]=p[mid][i];
    Build(tr[k].l,l,mid-1,d^1); Build(tr[k].r,mid+1,r,d^1);
    Update(k);
}

#undef mid

void Pushdown(int k){
    int l=tr[k].l,r=tr[k].r;
    if(tr[k].tag!=-1){
        if(l) tr[l].t.col=tr[l].tag=tr[k].tag;
        if(r) tr[r].t.col=tr[r].tag=tr[k].tag;
        tr[k].tag=-1;
    }
}

inline bool cover(int a,int b,int c,int d,int x1,int y1,int x2,int y2){
    return a<=x1 && c>=x2 && b>=y1 && d<=y2;
}

inline bool out(int a,int b,int c,int d,int x1,int y1,int x2,int y2){
    return a<x2 || c>x1 || b>y2 || d<y1;
}

void Modify(int k,int x1,int y1,int x2,int y2,int co){
    Pushdown(k);
    if(cover(tr[k].mx[0],tr[k].mi[1],tr[k].mi[0],tr[k].mx[1],x1,y1,x2,y2)){
        tr[k].t.col=co; tr[k].tag=co;
        return;
    }
    int l=tr[k].l,r=tr[k].r;
    if(cover(tr[k].t[0],tr[k].t[1],tr[k].t[0],tr[k].t[1],x1,y1,x2,y2)) tr[k].t.col=co;
    if(l && !out(tr[l].mx[0],tr[l].mi[1],tr[l].mi[0],tr[l].mx[1],x1,y1,x2,y2)) Modify(l,x1,y1,x2,y2,co);
    if(r && !out(tr[r].mx[0],tr[r].mi[1],tr[r].mi[0],tr[r].mx[1],x1,y1,x2,y2)) Modify(r,x1,y1,x2,y2,co);
}

int Query(int k,Point pt,int d){
    Pushdown(k); dim=d;
    if(pt[0]==tr[k].t[0] && pt[1]==tr[k].t[1]) return tr[k].t.col;
    if(pt<tr[k].t) return Query(tr[k].l,pt,d^1);
    else return Query(tr[k].r,pt,d^1);
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("4154.in","r",stdin);
    freopen("4154.out","w",stdout);
#endif
    int T;
    T=in();
    while(T--){
        n=in(); c=in(); q=in(); ind=timer=cnt=ans=0;
        memset(head,-1,sizeof(head));       
        for(int fa,i=2;i<=n;i++){
            fa=in(); addedge(fa,i);     
        }
        dfs(1);
        for(int i=1;i<=n;i++)
            p[i]=Point(dfn[i],dep[i],1,i);      
        Build(root,1,n,0);
        sort(p+1,p+1+n,cmp);
        for(int tmp,a,l,col,i=1;i<=q;i++){
            a=in(); l=in(); col=in();       
            if(col) Modify(root,last[a],dep[a],dfn[a],dep[a]+l,col);
            else ans=(1ll*i*Query(root,p[a],0)+ans)%mod;               
        }
        printf("%d\n",ans);
    }
    return 0;
}

BZOJ4520

这题跟之前题的套路差不多，枚举每个点进行查询，搞个优先队列记录一下前K个点就好了。因为这题会有重复，记录前2k个就避免算重了。

#include<queue>
#include<cstdio>
#include<cctype>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<algorithm>

#define maxn 100000+5
#define INF (LLONG_MAX-233)

using namespace std;

typedef long long LL;

int n,dim,cnt,root,K;
LL ans;

struct Point{
    int x[2];
    inline int operator [] (int i){ return x[i]; }
    inline bool operator < (const Point &T)const{
        if(x[dim]==T.x[dim]) return x[dim^1]<T.x[dim^1];
        return x[dim]<T.x[dim];
    }
}p[maxn];

struct KD_Tree{
    int l,r;
    int mi[2],mx[2];
    Point t;
}tr[maxn];

priority_queue <LL,vector<LL>,greater<LL> > q;

inline int in(){
    int x=0; char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(; isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x;
}

inline void Update_mx(int &x,int y){ if(y>x) x=y; }

inline void Update_mi(int &x,int y){ if(y<x) x=y; }

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

void Update(int k){
    for(int i=0;i<2;i++){
        if(tr[k].l) Update_mx(tr[k].mx[i],tr[tr[k].l].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].l].mi[i]);
        if(tr[k].r) Update_mx(tr[k].mx[i],tr[tr[k].r].mx[i]),Update_mi(tr[k].mi[i],tr[tr[k].r].mi[i]);
    }
}

#define mid ((l+r)>>1)

void Build(int &k,int l,int r,int d){
    if(l>r){ k=0; return; }
    dim=d; k=++cnt;
    nth_element(p+l,p+mid,p+r+1);
    tr[k].t=p[mid];
    for(int i=0;i<2;i++) tr[k].mi[i]=tr[k].mx[i]=p[mid][i];
    Build(tr[k].l,l,mid-1,d^1); Build(tr[k].r,mid+1,r,d^1);
    Update(k);
}

LL calc(int k,Point pt){
    LL res=0;
    for(int i=0;i<2;i++)
        res+=max(sqr(pt[i]-tr[k].mx[i]),sqr(pt[i]-tr[k].mi[i]));
    return res;
}

LL dis(Point a,Point b){
    return sqr(a[0]-b[0])+sqr(a[1]-b[1]);
}

void Query(int k,Point pt){
    LL tmp1=0,tmp2=0,tmp3=0;
    tmp1=dis(tr[k].t,pt);
    if(q.top()<tmp1) q.pop(),q.push(tmp1);
    if(tr[k].l) tmp2=calc(tr[k].l,pt);
    if(tr[k].r) tmp3=calc(tr[k].r,pt);  
    if(tmp2>tmp3){
        if(tr[k].l && q.top()<tmp2) Query(tr[k].l,pt);     
        if(tr[k].r && q.top()<tmp3) Query(tr[k].r,pt);      
    }
    else{
        if(tr[k].r && q.top()<tmp3) Query(tr[k].r,pt);
        if(tr[k].l && q.top()<tmp2) Query(tr[k].l,pt);  
    }
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("4520.in","r",stdin);
    freopen("4520.out","w",stdout);
#endif
    n=in(); K=in()*2;
    for(int i=1;i<=K;i++) q.push(0);
    for(int i=1;i<=n;i++){
        p[i].x[0]=in(); p[i].x[1]=in();                              
    }
    Build(root,1,n,0);
    for(int i=1;i<=n;i++)
        Query(root,p[i]);
    printf("%lld",q.top());
    return 0;   
}
标签：

相关文章