Submit: 588 Solved: 309
[Submit][Status][Discuss]
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
【题解】
第K远点对。是说C(N,2)个点对里面。点对之间的距离是第K远的。求这个距离。
我们枚举每个点。然后查看它与其他点的距离。
维护一个1..2*K远的队列。然后不断更新这个队列
(为什么是2*k,想想我们在枚举第一个点的时候，假如和第3个点配对，距离为第2远那么下次再枚举第3个点的时候还会遇到第一个点。又出现了一个第2远的数要加入到队列中。而这两个距离其实是同一个点对的。即排列。考虑其他第1,3,4,..k远的点对也会出现这种情况。我们就把K变成2*K。)；
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 109000;
int n, k,root,now;
long long duilie[300];
struct point
{
long long d[2], mi_n[2], ma_x[2] ;
int l,r;
};
point t[MAX_N],op;
void input_data()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &t[i].d[0], &t[i].d[1]);
}
bool cmp(point a, point b)
{
return a.d[now] < b.d[now];
}
void up_data(int rt)
{
int l = t[rt].l, r = t[rt].r;
for (int i = 0; i <= 1; i++)
{
if (l)
{
t[rt].ma_x[i] = max(t[rt].ma_x[i], t[l].ma_x[i]);
t[rt].mi_n[i] = min(t[rt].mi_n[i], t[l].mi_n[i]);
}
if (r)
{
t[rt].ma_x[i] = max(t[rt].ma_x[i], t[r].ma_x[i]);
t[rt].mi_n[i] = min(t[rt].mi_n[i], t[r].mi_n[i]);
}
}
}
int build(int begin, int end, int fx)
{
int m = (begin + end) >> 1;
now = fx;
nth_element(t + begin, t + m, t + end + 1, cmp);
for (int i = 0; i <= 1; i++)
t[m].ma_x[i] = t[m].mi_n[i] = t[m].d[i];
if (begin < m)
t[m].l = build(begin, m - 1, 1 - fx);
if (m < end)
t[m].r = build(m + 1, end, 1 - fx);
up_data(m);
return m;
}
long long sqr(long long x)
{
return x*x;
}
long long get_dis(int rt)
{
return sqr(t[rt].d[0] - op.d[0]) + sqr(t[rt].d[1] - op.d[1]);
}
long long gujia(int rt)//估价函数
{
long long temp = 0;
for (int i = 0; i <= 1; i++)
temp += max(sqr(t[rt].mi_n[i] - op.d[i]), sqr(t[rt].ma_x[i] - op.d[i]));
return temp;
}
void query(int rt)
{
long long dis = get_dis(rt);
int k_th = k;
while (duilie[k_th] <= dis)//找到这个距离在队列中的合适位置。
{
k_th--;
if (!k_th)
break;
}
if (k_th != k)
{
for (int i = k; i >= k_th + 2; i--)
duilie[i] = duilie[i - 1];//这个位置后面的数字往后挪。
duilie[k_th + 1] = dis;
}
int l = t[rt].l, r = t[rt].r;
long long gl = -1,gr = -1;
if (l)
gl = gujia(l);
if (r)
gr = gujia(r);
if (gl < gr)
{
if (gr >= duilie[k])
query(r);
if (gl >= duilie[k])
query(l);
}
else
{
if (gl >= duilie[k])
query(l);
if (gr >= duilie[k])
query(r);
}
}
void get_ans()
{
root = build(1, n, 0);
k = k * 2;//直接求2*k远
for (int i = 1; i <= k; i++)//duilie[1..k]分别表示第1,2,3..远。因此它是递减队列。
duilie[i] = 0;
for (int i = 1; i <= n; i++)
{
op.d[0] = t[i].d[0], op.d[1] = t[i].d[1];
query(root);
}
}
void output_ans()
{
printf("%lld
", duilie[k]);
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
input_data();
get_ans();
output_ans();
return 0;
}