本文版权归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;
}
