hdu 2966 In case of failure kd树

缘起

继续学习 kd树~ hdu 2966 In case of failure

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
给n个点，求对于每个点到最近点的欧几里德距离的平方。

【输入】
多样例. 首先第一行是样例数.每个样例开始于n, 然后n行是每个点的坐标x,y, 一个样例中没有两个点会重合的
2 <= n <= 10^5
0 <= x,y <=10^9

【输出】
每个样例输出n行, 每行是到第i个点的最近的点的距离的欧几里得距离的平方

【样例输入】
2
10
17 41
0 34
24 19
8 28
14 12
45 5
27 31
41 11
42 45
36 27
15
0 0
1 2
2 3
3 2
4 0
8 4
7 4
6 3
6 1
8 0
11 0
12 2
13 1
14 2
15 0

【样例输出】
200
100
149
100
149
52
97
52
360
97
5
2
2
2
5
1
1
2
4
5
5
2
2
2
5

【限制】
30s

kd树裸题. 用 【1】中板子虐之

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
#define SQUARE(x) ((x)*(x))
typedef long long LL;
const int maxn = 1e5+5, k = 2;
int n, depth, change[maxn],ans; // change[i]是原先input[i]变动到的kdTree的索引, kdTree[ans]是到当前考察的节点的最近点
LL ans_dis; // 最近欧式距离的平方

struct KdTreeNode
{
	LL x[k];
	int index;
	bool flag;
	bool operator<(const KdTreeNode &o) const
	{
		return x[depth]<o.x[depth];
	}
}kdTree[maxn<<2], input[maxn];

void build(int begin, int end, int cur, int dep)
{
	if (begin>end) return;
	depth = dep%k;
	int mid = (begin+end)>>1;
	nth_element(input+begin, input+mid, input+end+1);
	kdTree[cur] = input[mid];
	kdTree[cur].flag = true;
	change[input[mid].index] = cur; // 原先input[mid].index这个输入变动到了kdTree[cur]
	build(begin, mid-1, cur<<1, dep+1);
	build(mid+1, end, cur<<1|1, dep+1);
}

void query(int target, int cur, int dep)
{
	if (!kdTree[cur].flag) return;
	if (cur != target) // 考察当前节点 取最小距离不能和自己, 不是自己才去更新ans和ans_dis
	{
		LL dis = SQUARE(kdTree[target].x[0]-kdTree[cur].x[0])+SQUARE(kdTree[target].x[1]-kdTree[cur].x[1]);
		if (!ans || dis<ans_dis)
		{
			ans = cur;
			ans_dis = dis;
		}
	}
	int idm = dep%k;
	int tx = kdTree[target].x[idm]<kdTree[cur].x[idm]?(cur<<1):(cur<<1|1);
	int ty = tx^1;
	query(target, tx, dep+1);
	if (SQUARE(kdTree[target].x[idm]-kdTree[cur].x[idm])<ans_dis)
	{
		query(target, ty, dep+1);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d", &n);
		memset(kdTree, 0, sizeof(kdTree));
		for (int i = 1; i<=n; i++)
		{
			scanf("%lld%lld", &input[i].x[0], &input[i].x[1]);
			input[i].index = i;
		}
		build(1,n,1,0);
		for (int i = 1;i<=n;i++)
		{
			ans=0, ans_dis=1LL<<60;
			query(change[i], 1, 0);
			printf("%lld\n", ans_dis);
		}
	}
	return 0;
}

ac情况 水过水过~

Status Accepted
Time 2152ms
Memory 13336kB
Length 1885
Lang G++
Submitted 2019-09-22 17:28:11
Shared
RemoteRunId 30676678

参考

【1】https://yfsyfs.github.io/2019/09/21/hdu-5992-Finding-Hotels-kd%E6%A0%91/