【52.55%】【BZOJ 4520】K远点对

Time Limit: 30 Sec Memory Limit: 512 MB

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

Sample Output

【题解】

第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\n", duilie[k]);

}

int main()

{

	//freopen("F:\\rush.txt", "r", stdin);

	input_data();

	get_ans();

	output_ans();

	return 0;

}

巴特西