BZOJ4520 [Cqoi2016]K远点对

时间：2024-08-23 11:05:38

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

Description

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

Input

输入文件第一行为用空格隔开的两个整数 N， K。接下来 N 行，每行两个整数 X,Y，表示一个点
的坐标。1 < =  N < =  100000， 1 < =  K < =  100， K < =  N*(N−1)/2 ， 0 < =  X, Y < 2^31。

Output

输出文件第一行为一个整数，表示第 K 远点对的距离的平方（一定是个整数）。

Sample Input

10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1

Sample Output

9

正解：kd-tree

解题报告：

　　这题要求欧氏距离下的第k远点对。

　　我们考虑上$kd-tree$。$kd-tree$可以支持我们对于某一个给定的点与$kd-tree$中的点的距离最值查询，那么我们很容易发现，我们只需要对于每个点都分别与其他所有点求距离，最后对于全局取第$2*k$大的距离即可（因为每个距离我们算了两次）。

　　但是直接暴力的话会变成$ n^2 $，如果改在$kd-tree$上查询的话就可以大大节约时间，可以减掉大量无用状态。具体做法就是，维护一个大小为$2*k$的小根堆，对于每个点在$kd-tree$上查询与其他点的距离，如果大于堆顶，则删掉堆顶元素，把当前距离加入堆顶。最后只需输出堆顶元素即可。

　　kd-tree在这里就是优化暴力......

//It is made by ljh2000

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long LL;

const int MAXN = 100011;

int n,k,nowD,root,ql,qr;

struct node{ LL dis; inline bool operator < (const node &a) const { return a.dis<dis; } }tmp;

struct KDTree{ int d[2],Min[2],Max[2],l,r; }t[MAXN];

inline bool cmp(KDTree q,KDTree qq){ if(q.d[nowD]==qq.d[nowD]) return q.d[nowD^1]<qq.d[nowD^1]; return q.d[nowD]<qq.d[nowD]; }

inline void MAX(KDTree &q,KDTree qq,int type){ if(qq.Max[type]>q.Max[type]) q.Max[type]=qq.Max[type]; }

inline void MIN(KDTree &q,KDTree qq,int type){ if(qq.Min[type]<q.Min[type]) q.Min[type]=qq.Min[type]; }

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

inline LL getdis(int x,int y){ return sqr(t[x].d[0]-t[y].d[0])+sqr(t[x].d[1]-t[y].d[1]); }

inline LL almost_dis(KDTree q,KDTree qq){return max(sqr(q.d[0]-qq.Min[0]),sqr(q.d[0]-qq.Max[0]))+max(sqr(q.d[1]-qq.Min[1]),sqr(q.d[1]-qq.Max[1]));}

priority_queue<node>Q;

inline int getint(){

    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();

    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;

}

inline void update(int x){

	if(t[x].l) for(int i=0;i<2;i++) MAX(t[x],t[t[x].l],i),MIN(t[x],t[t[x].l],i);

	if(t[x].r) for(int i=0;i<2;i++) MAX(t[x],t[t[x].r],i),MIN(t[x],t[t[x].r],i);

}

inline int build(int l,int r,int D){

	nowD=D; int mid=(l+r)>>1; nth_element(t+l+1,t+mid+1,t+r+1,cmp);

	if(l<mid) t[mid].l=build(l,mid-1,D^1);

	if(mid<r) t[mid].r=build(mid+1,r,D^1);

	t[mid].Min[0]=t[mid].Max[0]=t[mid].d[0];

	t[mid].Min[1]=t[mid].Max[1]=t[mid].d[1];

	update(mid);

	return mid;

}

inline void query(int u){

	LL dl=0,dr=0,dd=getdis(0,u); if(dd>Q.top().dis) Q.pop(),tmp.dis=dd,Q.push(tmp);

	if(t[u].l) dl=almost_dis(t[0],t[t[u].l]); if(t[u].r) dr=almost_dis(t[0],t[t[u].r]);

	tmp=Q.top();

	if(dl>dr) {

		if(dl>tmp.dis) query(t[u].l); tmp=Q.top();

		if(dr>tmp.dis) query(t[u].r);

	}

	else{

		if(dr>tmp.dis) query(t[u].r); tmp=Q.top();

		if(dl>tmp.dis) query(t[u].l);

	}

}

inline void work(){

	n=getint(); k=getint(); for(int i=1;i<=n;i++) t[i].d[0]=getint(),t[i].d[1]=getint();

	root=build(1,n,0); tmp.dis=0;

	for(int i=1;i<=k*2;i++) Q.push(tmp);

	for(int i=1;i<=n;i++) {

		t[0].d[0]=t[i].d[0]; t[0].d[1]=t[i].d[1];

		query(root);

	}

	printf("%lld",Q.top().dis);

}

int main()

{

    work();

    return 0;

}

　　

相关文章