Blackops

初心易得，始终难守

0%

HDU 5992 Finding Hotels（三维KD-tree）

发表于 分类于 ， ，

Finding Hotels

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 1086 Accepted Submission(s): 304

Problem Description
There are N hotels all over the world. Each hotel has a location and a price. M guests want to find a hotel with an acceptable price and a minimum distance from their locations. The distances are measured in Euclidean metric.

Input
The first line is the number of test cases. For each test case, the first line contains two integers N (N ≤ 200000) and M (M ≤ 20000). Each of the following N lines describes a hotel with 3 integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N), in which x and y are the coordinates of the hotel, c is its price. It is guaranteed that each of the N hotels has distinct x, distinct y, and distinct c. Then each of the following M lines describes the query of a guest with 3 integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N), in which x and y are the coordinates of the guest, c is the maximum acceptable price of the guest.

Output
For each guests query, output the hotel that the price is acceptable and is nearest to the guests location. If there are multiple hotels with acceptable prices and minimum distances, output the first one.

Sample Input
2
3 3
1 1 1
3 2 3
2 3 2
2 2 1
2 2 2
2 2 3
5 5
1 4 4
2 1 2
4 5 3
5 2 1
3 3 5
3 3 1
3 3 2
3 3 3
3 3 4
3 3 5

Sample Output
1 1 1
2 3 2
3 2 3
5 2 1
2 1 2
2 1 2
1 4 4
3 3 5

题目链接：HDU 5992
很久以前就想学$KD-tree$来着，然而一直都看不懂直到补这题的时候发现代码简单明了，还真的跟$BST$一样
然后发现KD-tree其实是个真·点树，因为他一个树上的节点刚好对应一个空间里的点，即$[l,r]$自己的节点是$[mid,mid]$左子树是$[l,mid-1]$,右子树是$[mid+1,r]$，这样一来一个空间点刚好对应一个树上节点，那么如果用动态建树来构造$KD-tree$的话空间复杂度就是$O(N)$的了。
想到这里赶紧写了一发动态建树想一发AC，结果由于很久没写动态建树把记录节点个数的$sz$拿去当根节点$rt$来用了……WA了一个晚上，然后看了下以前写的$treap$才发现是这个低级错误（弱校选手真的惨……）
给一个学习$KD-tree$很好的博客：AC_dreamer大佬

然后讲一下我的理解：$KD-tree$就是按照节点深度来得到这个深度应该管理的某一维度$dim(dimension)$，不用管其他的维度，正是因为这个特性，所以节点存坐标的时候最好不要分开存，就用数组代表点在空间，这样既可以当成向量，也可以用全局变量更方便地排序。用$d[0]$和$d[1]$表示两个坐标值，$d[2]$表示hotel的价格，某一深度层的节点就是按照某维度排序，当做关键字来构造$BST$，然后查询的时候先估计一下个各个子树预计最长距离为多少，然后按优先顺序去$dfs$，当然某个点管辖范围内的最低旅馆价格如果都大于接受价格，说明这个点和其管辖的点集内均不存在符合要求的点，预估计距离就是$\infty$。

代码：

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 200010;
int idx;
struct KD
{
    int ls, rs, v, id;
    int d[3], mn[3], mx[3];
} T[N];
struct info
{
    int d[3], id;
    bool operator<(const info &rhs)const
    {
        return d[idx] < rhs.d[idx];
    }
} arr[N];
int rt, sz, rev[N];
pair<LL, int> ans;

void init()
{
    rt = sz = 0;
}
inline void pushup(int k)
{
    int ls = T[k].ls, rs = T[k].rs;
    if (ls)
    {
        for (int i = 0; i < 3; ++i)
        {
            T[k].mn[i] = min(T[k].mn[i], T[ls].mn[i]);
            T[k].mx[i] = max(T[k].mx[i], T[ls].mx[i]);
        }
    }
    if (rs)
    {
        for (int i = 0; i < 3; ++i)
        {
            T[k].mn[i] = min(T[k].mn[i], T[rs].mn[i]);
            T[k].mx[i] = max(T[k].mx[i], T[rs].mx[i]);
        }
    }
}
void build(int &k, int l, int r, int dim)
{
    k = ++sz;
    int mid = MID(l, r);
    idx = dim % 3;
    nth_element(arr + l, arr + mid, arr + r + 1);
    for (int i = 0; i < 3; ++i)
        T[k].d[i] = T[k].mn[i] = T[k].mx[i] = arr[mid].d[i];
    T[k].id = arr[mid].id;
    rev[arr[mid].id] = mid;
    T[k].ls = T[k].rs = 0;
    if (l < mid)
        build(T[k].ls, l, mid - 1, dim + 1);
    if (mid < r)
        build(T[k].rs, mid + 1, r, dim + 1);
    pushup(k);
}
inline LL sqr(const LL &x)
{
    return x * x;
}
inline LL dis(const info &a, const KD &b)
{
    return sqr((LL)a.d[0] - (LL)b.d[0]) + sqr((LL)a.d[1] - (LL)b.d[1]);
}
inline LL partionMin(const info &tar, int k)
{
    if (T[k].mn[2] > tar.d[2])
        return INF;
    LL ret = 0;
    if (tar.d[0] > T[k].mx[0])
        ret += sqr(tar.d[0] - T[k].mx[0]);
    if (tar.d[0] < T[k].mn[0])
        ret += sqr(T[k].mn[0] - tar.d[0]);
    if (tar.d[1] > T[k].mx[1])
        ret += sqr(tar.d[1] - T[k].mx[1]);
    if (tar.d[1] < T[k].mn[1])
        ret += sqr(T[k].mn[1] - tar.d[1]);
    return ret;
}
void FindMin(int k, const info &tar)
{
    LL dm = dis(tar, T[k]);
    if (T[k].d[2] <= tar.d[2] && (dm < ans.first || (dm == ans.first && T[k].id < ans.second)))
        ans = {dm, T[k].id};
    int ls = T[k].ls;
    int rs = T[k].rs;
    LL dl = ls ? partionMin(tar, ls) : INF;
    LL dr = rs ? partionMin(tar, rs) : INF;
    if (dl < dr)
    {
        if (dl <= ans.first)
            FindMin(ls, tar);
        if (dr <= ans.first)
            FindMin(rs, tar);
    }
    else
    {
        if (dr <= ans.first)
            FindMin(rs, tar);
        if (dl <= ans.first)
            FindMin(ls, tar);
    }
}
int main(void)
{
    int TC;
    int n, m, i;
    scanf("%d", &TC);
    while (TC--)
    {
        init();
        scanf("%d%d", &n, &m);
        for (i = 1; i <= n; ++i)
        {
            scanf("%d%d%d", &arr[i].d[0], &arr[i].d[1], &arr[i].d[2]);
            arr[i].id = i;
        }
        build(rt, 1, n, 0);
        for (i = 1; i <= m; ++i)
        {
            info tar;
            scanf("%d%d%d", &tar.d[0], &tar.d[1], &tar.d[2]);
            ans.first = INF + 1;
            FindMin(1, tar);
            int x = rev[ans.second];
            printf("%d %d %d\n", arr[x].d[0], arr[x].d[1], arr[x].d[2]);
        }
    }
    return 0;
}