初见K-D Tree
其实这样的题(欧几里得距离第$x$近点对)不应该用K-D Tree做，因为会被构造数据卡成$O(n^2)$，随机的另说。
但是并没有找到合适的K-D Tree的题(区域统计)，于是就凑活着写了，代码极丑预警
1 // luogu-judger-enable-o2 2 #include<queue> 3 #include<cstdio> 4 #include<cctype> 5 #include<cstring> 6 #include<algorithm> 7 using namespace std; 8 const int N=100005; 9 const long long inf=1e9; 10 struct a 11 { 12 int id; 13 long long ds; 14 }; 15 bool operator < (a x,a y) 16 { 17 return x.ds==y.ds?x.id<y.id:x.ds>y.ds; 18 } 19 priority_queue<a> hp; 20 struct b 21 { 22 int ps[2],mn[2],mx[2],sn[2],id,idn; 23 }kdt[N],qry; 24 int n,m,k,r,f,typ; 25 inline void read(int &x) 26 { 27 x=0,f=0; char ch=getchar(); 28 while(!isdigit(ch)) 29 f|=ch=='-',ch=getchar(); 30 while(isdigit(ch)) 31 x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); 32 x=f?-x:x; 33 } 34 void write(int x) 35 { 36 if(x>9) write(x/10); 37 putchar(x%10^48); 38 } 39 bool operator < (b x,b y) 40 { 41 return x.ps[typ]<y.ps[typ]; 42 } 43 void Pushup(int nde) 44 { 45 kdt[nde].idn=kdt[nde].id; 46 int lson=kdt[nde].sn[0],rson=kdt[nde].sn[1]; 47 b ls=kdt[lson],rs=kdt[rson]; 48 if(lson) kdt[nde].idn=min(kdt[nde].idn,ls.idn); 49 if(rson) kdt[nde].idn=min(kdt[nde].idn,rs.idn); 50 for(int i=0;i<=1;i++) 51 { 52 kdt[nde].mn[i]=kdt[nde].mx[i]=kdt[nde].ps[i]; 53 if(lson) kdt[nde].mn[i]=min(kdt[nde].mn[i],ls.mn[i]),kdt[nde].mx[i]=max(kdt[nde].mx[i],ls.mx[i]); 54 if(rson) kdt[nde].mn[i]=min(kdt[nde].mn[i],rs.mn[i]),kdt[nde].mx[i]=max(kdt[nde].mx[i],rs.mx[i]); 55 } 56 } 57 int Create(int l,int r,int k) 58 { 59 typ=k; int mid=(l+r)/2; 60 nth_element(kdt+l,kdt+mid,kdt+r+1); 61 if(l<mid) kdt[mid].sn[0]=Create(l,mid-1,k^1); 62 if(r>mid) kdt[mid].sn[1]=Create(mid+1,r,k^1); 63 Pushup(mid); return mid; 64 } 65 long long calc1(int nde) 66 { 67 long long mnx=kdt[nde].mn[0]-qry.ps[0],mxx=kdt[nde].mx[0]-qry.ps[0]; 68 long long mny=kdt[nde].mn[1]-qry.ps[1],mxy=kdt[nde].mx[1]-qry.ps[1]; 69 return max(mnx*mnx,mxx*mxx)+max(mny*mny,mxy*mxy); 70 } 71 long long calc2(int nde) 72 { 73 long long dsx=kdt[nde].ps[0]-qry.ps[0]; 74 long long dsy=kdt[nde].ps[1]-qry.ps[1]; 75 return dsx*dsx+dsy*dsy; 76 } 77 inline bool farther(long long x,long long y) 78 { 79 a t=hp.top(); 80 return x>t.ds||(x==t.ds&&y<t.id); 81 } 82 inline bool further(long long x,long long y) 83 { 84 a t=hp.top(); 85 return x>t.ds||(x==t.ds&&kdt[y].idn<t.id); 86 } 87 void Query(int nde) 88 { 89 b tmp=kdt[nde]; long long dis=calc2(nde); 90 int idx=tmp.id,lson=tmp.sn[0],rson=tmp.sn[1]; 91 if(farther(dis,idx)) 92 hp.pop(),hp.push((a){idx,dis}); 93 long long d1=lson?calc1(lson):-inf,d2=rson?calc1(rson):-inf; 94 if(d1>d2) 95 { 96 if(further(d1,lson)) Query(lson); 97 if(further(d2,rson)) Query(rson); 98 } 99 else 100 { 101 if(further(d2,rson)) Query(rson); 102 if(further(d1,lson)) Query(lson); 103 } 104 } 105 int main() 106 { 107 register int i; 108 read(n); 109 for(i=1;i<=n;i++) 110 read(kdt[i].ps[0]),read(kdt[i].ps[1]),kdt[i].id=i; 111 r=Create(1,n,0),scanf("%d",&m); 112 while(m--) 113 { 114 while(!hp.empty()) hp.pop(); 115 read(qry.ps[0]),read(qry.ps[1]),read(k); 116 for(i=1;i<=k;i++) hp.push((a){0,-inf}); 117 Query(r),write(hp.top().id),puts(""); 118 } 119 return 0; 120 }