【BZOJ4520】[Cqoi2016]K远点对

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

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

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <queue>#define rep for(int i=0;i<=1;i++)#define x2(_) ((_)*(_))using namespace std;const int maxn=100010;typedef long long ll;struct kd{	 ll v[2],sm[2],sn[2];	 int ls,rs;	 ll & operator [] (int a) {return v[a];}	 kd (){}	 kd (ll a,ll b){v[0]=sm[0]=sn[0]=a,v[1]=sm[1]=sn[1]=b,ls=rs=0;}}t[maxn];priority_queue<ll> pq;int n,m,D,root,now;ll A,B;bool cmp(kd a,kd b){	return (a[D]==b[D])?(a[D^1]<b[D^1]):(a[D]<b[D]);}void pushup(int x,int y){	rep t[x].sm[i]=max(t[x].sm[i],t[y].sm[i]),t[x].sn[i]=min(t[x].sn[i],t[y].sn[i]);}int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int build(int l,int r,int d){	if(l>r)	return 0;	int mid=l+r>>1;	D=d,nth_element(t+l,t+mid,t+r+1,cmp);	t[mid].ls=build(l,mid-1,d^1),t[mid].rs=build(mid+1,r,d^1);	if(t[mid].ls)	pushup(mid,t[mid].ls);	if(t[mid].rs)	pushup(mid,t[mid].rs);	return mid;}ll getdis(int x){	return max(x2(t[x].sm[0]-A),x2(t[x].sn[0]-A))+max(x2(t[x].sm[1]-B),x2(t[x].sn[1]-B));}void query(int x){	if(!x||getdis(x)<=-pq.top())	return ;	if(x!=now&&x2(t[x][0]-A)+x2(t[x][1]-B)>-pq.top())	pq.push(-x2(t[x][0]-A)-x2(t[x][1]-B)),pq.pop();	if(getdis(t[x].ls)>getdis(t[x].rs))	query(t[x].ls),query(t[x].rs);	else	query(t[x].rs),query(t[x].ls);}int main(){	n=rd(),m=rd();	int i,a,b;	for(i=1;i<=n;i++)	a=rd(),b=rd(),t[i]=kd(a,b);	for(i=1;i<=2*m;i++)	pq.push(0);	root=build(1,n,0);	for(i=1;i<=n;i++)	now=i,A=t[i].v[0],B=t[i].v[1],query(root);	printf("%lld\n",-pq.top());	return 0;}