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
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1
Sample Output
9
Solution
到现在为止只会写K-D Tree的板子题……
这次画了个图又理解了一下估价函数，感觉挺不错的
按照套路维护k远开个堆就好了，只不过由于这个题(x,y)和(y,x)算一对
需要开2*k的堆最后输出堆顶
这次画了个图又理解了一下估价函数，感觉挺不错的
按照套路维护k远开个堆就好了，只不过由于这个题(x,y)和(y,x)算一对
需要开2*k的堆最后输出堆顶
Code
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#define N (100000+1000)
#define INF 1e17
using namespace std; struct P
{
long long dis,num;
bool operator < (const P &a) const{return dis>a.dis;}
}po;
long long n,k,D,Root;
priority_queue<P>q; struct Node
{
long long d[],Max[],Min[],lson,rson;
bool operator < (const Node &a) const {return d[D]<a.d[D];}
}p[N],T; struct KDT
{
Node Tree[N];
long long sqr(long long x){return x*x;} void Update(long long now)
{
for (int i=; i<=; ++i)
{
long long ls=Tree[now].lson, rs=Tree[now].rson;
Tree[now].Max[i]=Tree[now].Min[i]=Tree[now].d[i];
if (ls)
{
Tree[now].Max[i]=max(Tree[now].Max[i],Tree[ls].Max[i]);
Tree[now].Min[i]=min(Tree[now].Min[i],Tree[ls].Min[i]);
}
if (rs)
{
Tree[now].Max[i]=max(Tree[now].Max[i],Tree[rs].Max[i]);
Tree[now].Min[i]=min(Tree[now].Min[i],Tree[rs].Min[i]);
}
}
}
long long Build(long long opt,long long l,long long r)
{
if (l>r) return ;
long long mid=(l+r)>>;
D=opt; nth_element(p+l,p+mid,p+r+);
Tree[mid]=p[mid];
Tree[mid].lson=Build(opt^,l,mid-);
Tree[mid].rson=Build(opt^,mid+,r);
Update(mid); return mid;
}
long long Get_max(long long now)
{
long long ans=;
for (int i=; i<=; ++i)
ans+=max(sqr(T.d[i]-Tree[now].Min[i]),sqr(T.d[i]-Tree[now].Max[i]));
return ans;
}
void Query(long long now)
{
long long ls=Tree[now].lson, rs=Tree[now].rson, lans=-INF, rans=-INF;
if (ls) lans=Get_max(ls);
if (rs) rans=Get_max(rs); po.dis=sqr(T.d[]-Tree[now].d[])+sqr(T.d[]-Tree[now].d[]); po.num=now;
if (po.dis>q.top().dis)
q.pop(),q.push(po); if (lans>rans)
{
if (lans>q.top().dis) Query(ls);
if (rans>q.top().dis) Query(rs);
}
else
{
if (rans>q.top().dis) Query(rs);
if (lans>q.top().dis) Query(ls);
}
}
}KDT; int main()
{
scanf("%lld%lld",&n,&k);
for (int i=; i<=n; ++i)
scanf("%lld%lld",&p[i].d[],&p[i].d[]);
Root=KDT.Build(,,n); po.dis=-INF,po.num=;
for (int i=; i<=*k; ++i)
q.push(po); for (int i=; i<=n; ++i)
{
T=KDT.Tree[i];
KDT.Query(Root);
}
printf("%lld",q.top().dis);
}