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

分析： kdtree 因为每个点对我们会计算两次((x,y)&(y,x)) 所以我们为了避免判重的繁琐 我们干脆k*=2

需要注意一下的是dis的计算 做了好几道题后，我们发现在计算最近点和最远点时， dis的写法是不一样的

tip

一开始连样例都过不了 问题就在这一句！！！ 这是什么道理呢

C++优先队列的基本使用方法 priority_queue q;//普通的优先级队列，按从大到小排序

priority_queue < int, vector < int > , greater < int > > q; //从小到大的优先级队列，可将greater改为less，即为从大到小

priority_queue < node > q;//必须要重载运算符 运用

了解更多

因为我们要找第k远的点对，所以在插入的时候 一定是拿出一个队列中最小的元素与当前值进行比较

后来狂WA不止 经过一个小时的排查，发现是一个函数中应该返回ll但是我没有强制类型转换

这里写代码片 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define ll long long using namespace std; const int N=100010; struct node{ int l,r,d[2],mn[2],mx[2]; }; node t[N]; int n,k,root,cmpd,x,y; priority_queue<ll,vector<ll>,greater<ll> >q; //// int cmp(const node &a,const node &b) { return ((a.d[cmpd]<b.d[cmpd])||((a.d[cmpd]==b.d[cmpd])&&(a.d[!cmpd]<b.d[!cmpd]))); } ll maxx(ll x,ll y) {if (x>y) return x;else return y;} ll sqr(int x){return (ll)x*x;} void update(int bh) { int lc=t[bh].l; int rc=t[bh].r; if (lc) { t[bh].mn[0]=min(t[bh].mn[0],t[lc].mn[0]); t[bh].mn[1]=min(t[bh].mn[1],t[lc].mn[1]); t[bh].mx[0]=max(t[bh].mx[0],t[lc].mx[0]); t[bh].mx[1]=max(t[bh].mx[1],t[lc].mx[1]); } if (rc) { t[bh].mn[0]=min(t[bh].mn[0],t[rc].mn[0]); t[bh].mn[1]=min(t[bh].mn[1],t[rc].mn[1]); t[bh].mx[0]=max(t[bh].mx[0],t[rc].mx[0]); t[bh].mx[1]=max(t[bh].mx[1],t[rc].mx[1]); } } int build(int l,int r,int D) { cmpd=D; int mid=(l+r)>>1; nth_element(t+l+1,t+mid+1,t+1+r,cmp); ////////// t[mid].mn[0]=t[mid].mx[0]=t[mid].d[0]; t[mid].mn[1]=t[mid].mx[1]=t[mid].d[1]; if (l!=mid) t[mid].l=build(l,mid-1,!D); if (r!=mid) t[mid].r=build(mid+1,r,!D); update(mid); return mid; } ll dis(int now,int x,int y) //max距离的算法 { ll d=0; d+=maxx(sqr(t[now].mn[0]-x),sqr(t[now].mx[0]-x)); d+=maxx(sqr(t[now].mn[1]-y),sqr(t[now].mx[1]-y)); return d; } void ask(int now) { ll d0,dl,dr; d0=sqr(x-t[now].d[0])+sqr(y-t[now].d[1]); if (t[now].l) dl=dis(t[now].l,x,y); else dl=0; if (t[now].r) dr=dis(t[now].r,x,y); else dr=0; if (d0>q.top()) q.pop(),q.push(d0); if (dl>dr) //最远距离 { if (dl>q.top()) ask(t[now].l); if (dr>q.top()) ask(t[now].r); } else { if (dr>q.top()) ask(t[now].r); if (dl>q.top()) ask(t[now].l); } } int main() { scanf("%d%d",&n,&k); k*=2; for (int i=1;i<=k;i++) q.push(0); //////// for (int i=1;i<=n;i++) scanf("%d%d",&t[i].d[0],&t[i].d[1]); root=build(1,n,0); for (int i=1;i<=n;i++) { x=t[i].d[0]; y=t[i].d[1]; ask(root); } printf("%lld",q.top()); return 0; }