「hdu2966」In case of failure

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(t15)t (t \leq 15) that follow. Each test cases begin with the number of Cash Machines n(2n105)n (2 \leq n \leq 10^5). Each of the next n lines contain the coordinates of one Cash Machine x,y(0x,y109)x,y (0 \leq x,y \leq 10^9) separated by a space.
No two points in one test case will coincide.

Output

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

Sample Input

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

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

Source

Central European Programming Contest 2008

Solution

题意就是要对输入的每一个点输出距离他最近的点的距离的最小值的平方。距离指欧几里得距离。
KdTree的模板题
查询的时候是查询到左右儿子矩阵的最近点的距离,不是四个角的距离。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e5 + 66;
int n, rt, tot;
struct P {
ll x, y;
}a[N], b[N];
bool cmpx(P _x, P _y) {
return _x.x < _y.x;
}
bool cmpy(P _x, P _y) {
return _x.y < _y.y;
}
struct Tree {
P p;
ll x1, x2, y1, y2;
int l, r;
}t[N];
const int inf = 1e9 + 7;
void build(int &jd, int l, int r, bool c) {
jd = ++tot;
int mid = (l + r) >> 1;
if(!c) nth_element(a + l, a + mid, a + r + 1, cmpx);
else nth_element(a + l, a + mid, a + r + 1, cmpy);
t[jd].p = a[mid];
t[jd].x1 = t[jd].y1 = inf;
t[jd].x2 = t[jd].y2 = -inf;
for(int i = l; i <= r; ++i) {
t[jd].x1 = min(t[jd].x1, a[i].x);
t[jd].x2 = max(t[jd].x2, a[i].x);
t[jd].y1 = min(t[jd].y1, a[i].y);
t[jd].y2 = max(t[jd].y2, a[i].y);
}
if(l < mid) build(t[jd].l, l, mid - 1, c ^ 1);
if(r > mid) build(t[jd].r, mid + 1, r, c ^ 1);
}
ll ans;
ll dst(ll x1, ll y1, ll x2, ll y2) {
return sqr(x1 - x2) + sqr(y1 - y2);
}
ll getdis(P x, int y) {
ll res = 0;
if(t[y].x2 < x.x) res = sqr(t[y].x2 - x.x);
else if(t[y].x1 > x.x) res = sqr(t[y].x1 - x.x);
if(t[y].y2 < x.y) res += sqr(t[y].y2 - x.y);
else if(t[y].y1 > x.y) res += sqr(t[y].y1 - x.y);
return res;
}
void query(int jd, P &x) {
if(t[jd].p.x != x.x || t[jd].p.y !=x.y)ans = min(ans, dst(x.x, x.y, t[jd].p.x, t[jd].p.y));
ll lt = 1e18 + 666, rt = 1e18 + 666;
if(t[jd].l) lt = getdis(x, t[jd].l);
if(t[jd].r) rt = getdis(x, t[jd].r);
if(lt < rt) { //优化
if(lt < ans) query(t[jd].l, x);
if(rt < ans) query(t[jd].r, x);
} else {
if(rt < ans) query(t[jd].r, x);
if(lt < ans) query(t[jd].l, x);
}
}
int main() {
int T = read();
while(T--) {
rt = tot = 0;
n = read();
for(int i = 1; i <= n; ++i)
a[i].x = read(), a[i].y = read(), b[i] = a[i];
build(rt, 1, n, 0);
for(int i = 1; i <= n; ++i) {
ans = 1e18 + 666;
query(rt, b[i]);
writeln(ans);
}
}
return 0;
}