P4357 [CQOI2016]K 远点对 题解

题目大意

已知平面内 (N) 个点的坐标，求欧氏距离下的第 (K) 远点对

P4357 [CQOI2016]K 远点对

solve

这很显然是一道 (kd-tree) 的模板题，所以我们考虑用 (kd-tree) 来处理

第 (i) 位分割的时候，可以考虑用去方差最大的维度为分割的维度，但由于这道题比较水，我用 (rand()) 就水过了

答案要求求第 (k) 远的点对，用一个堆来维护距离就可以了，每次和对顶比较，如果发现比堆顶小的，就把堆顶踢掉，然后加入新的节点

在查询的时候，左右区间判一下，如果这个区间中最远的点比当前堆顶小，这个区间没有必要遍历，所以这样能剪掉很多无用状态

code

#include<cstdio>
#include<queue>
#include<ctime>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int maxn=1000005,INF=1<<30;
int opt,N,K;
struct Pnt{int x[2];}G[maxn];
inline LL sqr(int x){return 1ll*x*x;}
inline bool cmp(Pnt a,Pnt b){return a.x[opt]<b.x[opt];}
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
priority_queue<LL>q;
struct Segment_tree{
	int max_n[maxn<<1][2],min_n[maxn<<1][2],l[maxn<<1],r[maxn<<1],cnt;
	Pnt d[maxn<<1];
	inline void pushup(int x){
		for(int i=0;i<2;i++){max_n[x][i]=min_n[x][i]=d[x].x[i];}
		if(l[x]){for(int i=0;i<2;i++){max_n[x][i]=max(max_n[x][i],max_n[l[x]][i]);min_n[x][i]=min(min_n[x][i],min_n[l[x]][i]);}}
		if(r[x]){for(int i=0;i<2;i++){max_n[x][i]=max(max_n[x][i],max_n[r[x]][i]);min_n[x][i]=min(min_n[x][i],min_n[r[x]][i]);}}
	}
	inline void build(int &x,int L,int R){
		if(L>R)return ;
		x=++cnt;
		int mid=(R-L>>1)+L;
		opt=rand()%2;
		nth_element(G+L,G+mid,G+R+1,cmp);d[x]=G[mid];
		build(l[x],L,mid-1);build(r[x],mid+1,R);
		pushup(x);
	}
	inline LL f(Pnt a,Pnt b){return sqr(a.x[0]-b.x[0])+sqr(a.x[1]-b.x[1]);}
	inline LL g(Pnt a,int b){return max(sqr(a.x[0]-max_n[b][0]),sqr(a.x[0]-min_n[b][0]))+max(sqr(a.x[1]-max_n[b][1]),sqr(a.x[1]-min_n[b][1]));}
	inline void query(int x,Pnt y){
		LL dl=-INF,dr=-INF;
		if(l[x])dl=g(y,l[x]);if(r[x])dr=g(y,r[x]);
		LL di=f(y,d[x]);
		if(-q.top()<di){q.pop();q.push(-di);}
		if(dl>dr){if(-q.top()<dl)query(l[x],y);if(-q.top()<dr)query(r[x],y);}
		else {if(-q.top()<dr)query(r[x],y);if(-q.top()<dl)query(l[x],y);}
	}
}T;
int main(){
	freopen("P4357.in","r",stdin);
	freopen("P4357.out","w",stdout);
	srand(time(NULL));
	N=read();K=read();
	for(int i=1;i<=N;i++) G[i].x[0]=read(),G[i].x[1]=read();
	for(int i=1;i<=(K<<1);i++) q.push(0);
	T.build(T.l[0],1,N);
	for(int i=1;i<=N;i++) T.query(1,G[i]);
	printf("%lld
",-q.top());
	return 0;
}