HYSBZ4520-K遠點對

[Cqoi2016]K遠點對

Time Limit: 30 Sec   Memory Limit: 512 MB

Submit: 904   Solved: 466

[ 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

9

HINT

Source

解題思路：kd-tree，建出kd-tree後，暴力枚舉每個點即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cctype>
#include <map>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

#define LL long long
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2000000 + 5;
const int demension = 2;//二維

struct node
{
	int pos[demension];
	int ma[demension], mi[demension];
	int l, r;
}a[N], x;
int cmpDem;//以第cmpDem維作比較
int root, n, m, Size;
priority_queue<LL, vector<LL>, greater<LL> >q;

bool cmp(const node &a, const node&b)
{
	if (a.pos[cmpDem] != b.pos[cmpDem]) return a.pos[cmpDem] < b.pos[cmpDem];
	else return a.pos[!cmpDem] < b.pos[!cmpDem];
}

void Merge(int k)
{
	for (int i = 0; i < demension; i++)
	{
		if (a[k].l)
		{
			a[k].ma[i] = max(a[k].ma[i], a[a[k].l].ma[i]);
			a[k].mi[i] = min(a[k].mi[i], a[a[k].l].mi[i]);
		}
		if (a[k].r)
		{
			a[k].ma[i] = max(a[k].ma[i], a[a[k].r].ma[i]);
			a[k].mi[i] = min(a[k].mi[i], a[a[k].r].mi[i]);
		}
	}
}

LL getdis(int k)
{
	LL dis = 0;
	for (int i = 0; i < demension; i++)
		dis += max(1LL * (a[k].mi[i] - x.pos[i]) * (a[k].mi[i] - x.pos[i]), 1LL * (x.pos[i] - a[k].ma[i]) * (x.pos[i] - a[k].ma[i]));
	return dis;
}

int build(int l, int r, int k)
{
	if (l > r) return 0;
	int mid = (l + r) / 2;
	//以第mid個元素為中心排序
	cmpDem = k;
	nth_element(a + l, a + mid, a + r + 1, cmp);
	//左右子樹
	a[mid].l = build(l, mid - 1, k ^ 1);
	a[mid].r = build(mid + 1, r, k ^ 1);
	Merge(mid);
	return mid;
}

void query(int k)
{
	LL dis = 0;
	for (int i = 0; i < demension; i++) dis += 1LL * (x.pos[i] - a[k].pos[i])*(x.pos[i] - a[k].pos[i]);
	if (Size < m) q.push(dis), Size++;
	else
	{
		LL pre = q.top();
		if (pre < dis) q.pop(), q.push(dis);
	}
	LL dl = a[k].l ? getdis(a[k].l) : -1, dr = a[k].r ? getdis(a[k].r) : -1;
	if (max(dl, dr) <= q.top() && Size >= m) return;
	if (dl > dr)
	{
		if (Size < m || dl > q.top()) query(a[k].l);
		if (Size < m || dr > q.top()) query(a[k].r);
	}
	else
	{
		if (Size < m || dr > q.top()) query(a[k].r);
		if (Size < m || dl > q.top()) query(a[k].l);
	}
}

int main()
{
	while (~scanf("%d%d", &n, &m))
	{
		for (int i = 1; i <= n; i++)
		{
			scanf("%d%d", &a[i].pos[0], &a[i].pos[1]);
			a[i].l = a[i].r = 0;
			a[i].ma[0] = a[i].mi[0] = a[i].pos[0];
			a[i].ma[1] = a[i].mi[1] = a[i].pos[1];
		}
		root = build(1, n, 0);
		m *= 2;
		Size = 0;
		for (int i = 1; i <= n; i++)
		{
			x = a[i];
			query(root);
		}
		printf("%lld\n", q.top());
		while (!q.empty()) q.pop();
	}
	return 0;
}