Blackops

初心易得，始终难守

0%

HDU 2966 In case of failure（二维KD-tree入门题）

发表于 分类于 ， ，

In case of failure

Time Limit: 60000/30000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2354 Accepted Submission(s): 985

Problem Description
To help their clients deal with faulty Cash Machines, the board of The Planar Bank has decided to stick a label expressing sincere regret and sorrow of the bank about the failure on every ATM. The very same label would gently ask the customer to calmly head to the nearest Machine (that should hopefully
work fine).

In order to do so, a list of two-dimensional locations of all n ATMs has been prepared, and your task is to find for each of them the one closest with respect to the Euclidean distance.

Input
The input contains several test cases. The very first line contains the number of cases t (t <= 15) that follow. Each test cases begin with the number of Cash Machines n (2 <= n <= 10^5). Each of the next n lines contain the coordinates of one Cash Machine x,y (0 <= x,y <=10^9) separated by a space. No two
points in one test case will coincide.

Output
For each test case output n lines. i-th of them should contain the squared distance between the i-th ATM from the input and its nearest neighbour.

Sample Input
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

Sample Output
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

题目链接：HDU 2966
$KD-tree$的入门题，每一维都当成$BST$，动态开点优化空间复杂度至$O(N)$就可以直接写完1A，当然自己显然不能和自己“最邻近”，因此除了记录最短距离还要记录最短距离的另一个点是谁，只有当这点不是自己时才能更新最短距离；最后由于建树过程中会对原数组排序变动，而题目要按输入顺序输出询问，因此再用一个$rev[]$数组映射一下第$i$的点在第变动后数组下标为$rev[i]$。
代码：

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#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 = 1e5 + 7;
typedef pair<LL, int > PL;

int idx;
struct KD
{
    int ls, rs, id;
    int d[2], mn[2], mx[2];
    bool operator<(const KD &rhs)const
    {
        return d[idx] < rhs.d[idx];
    }
} T[N], arr[N];
int sz, rt, rev[N];
PL ans;

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