解题关键:带插入kdtree模板题。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 1000005 #define inf (1<<30) using namespace std; int n,m,dim,rt,ans; struct node{int p[2],x[2],y[2];}a[N]; bool cmp(node x,node y){ return x.p[dim]<y.p[dim]; } struct kd_tree{ int c[N][2]; node s[N],q; void update(int k){//管辖范围 int l=c[k][0],r=c[k][1]; for(int i=0;i<2;i++){ if(l){ s[k].x[i]=min(s[k].x[i],s[l].x[i]); s[k].y[i]=max(s[k].y[i],s[l].y[i]); } if(r){ s[k].x[i]=min(s[k].x[i],s[r].x[i]); s[k].y[i]=max(s[k].y[i],s[r].y[i]); } } } void add(int k,node t){ for(int i=0;i<2;i++)s[k].x[i]=s[k].y[i]=s[k].p[i]=t.p[i]; } int dist(node t,int k){ int tmp=0; for(int i=0;i<2;i++) tmp+=max(0,s[k].x[i]-t.p[i]); for(int i=0;i<2;i++) tmp+=max(0,t.p[i]-s[k].y[i]); return tmp; }//? void build(int &k,int l,int r,int now){ k=(l+r)>>1; dim=now; nth_element(a+l,a+k,a+r+1,cmp); add(k,a[k]); if(l<k) build(c[k][0],l,k-1,now^1); if(k<r) build(c[k][1],k+1,r,now^1); update(k); } void ins(int k,int now){ if(q.p[now]<s[k].p[now]){ if(c[k][0]) ins(c[k][0],now^1); else c[k][0]=++n,add(n,q); } else{ if(c[k][1]) ins(c[k][1],now^1); else c[k][1]=++n,add(n,q); } update(k); } void qry(int k){//曼哈顿距离,且只求最短,dis是最短距离 int tmp=0; for(int i=0;i<2;i++) tmp+=abs(s[k].p[i]-q.p[i]); ans=min(ans,tmp); int dl=c[k][0]?dist(q,c[k][0]):inf,dr=c[k][1]?dist(q,c[k][1]):inf; if(dl<dr){ if(dl<ans) qry(c[k][0]); if(dr<ans) qry(c[k][1]); }else{ if(dr<ans) qry(c[k][1]); if(dl<ans) qry(c[k][0]); } } }kd; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].p[0],&a[i].p[1]); kd.build(rt,1,n,0); while(m--){ int k; scanf("%d%d%d",&k,&kd.q.p[0],&kd.q.p[1]); if(k==1) kd.ins(rt,0); else{ ans=inf; kd.qry(rt); printf("%d\n",ans); } } return 0; }