HDU 2966 In case of failure

In case of failure

http://acm.hdu.edu.cn/showproblem.php?pid=2966

题意：

　　　求平面上距离每个点最近的点。输出平方即可。

分析：

　　k-d tree模板题。k-d树的最近邻搜索。

　　关于k-d tree 划分平面：应该按照维度的方差的大小来划分，取最大的一维，由于这道题只有两维，而且对于每一层先按x，在按y的方案也是可以过的。还有可以按照维度最长的划分。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 
 5 const int N = 100010;
 6 const int DIM = 2; // dimension
 7 const LL INF = 1e18;
 8 
 9 struct Point{
10     LL x[2];
11 }ori[N],p[N],Q; // original point & point
12 int Cur;
13 
14 #define Root 1,n,1
15 #define lson l,m-1,D+1
16 #define rson m+1,r,D+1
17 
18 bool cmp(Point a,Point b) {
19     return a.x[Cur] < b.x[Cur];
20 }
21 LL sqr(LL x) {
22     return x * x;
23 }
24 LL dist(Point a,Point b) {
25     LL res = 0;
26     for (int i=0; i<DIM; ++i) 
27         res += sqr(a.x[i] - b.x[i]);
28     return res ? res : INF;
29 }
30 void build(int l,int r,int D) {
31     if (l >= r) return ;
32     int m = (l + r) >> 1;
33     Cur = D & 1;
34     nth_element(p+l, p+m, p+r+1, cmp);
35     build(lson);
36     build(rson);
37 }
38 LL query(int l,int r,int D) {
39     int cur = D & 1;
40     if (l >= r) {
41         if (l == r)  return dist(Q, p[l]);
42         else return INF;
43     }
44     int m = (l + r ) >> 1;
45     LL res = dist(Q, p[m]),tmp;
46     if (Q.x[cur] < p[m].x[cur]) {
47         tmp = query(lson);
48         if (tmp > sqr(Q.x[cur] - p[m].x[cur])) tmp = min(tmp, query(rson));
49     }
50     else {
51         tmp = query(rson);
52         if (tmp > sqr(Q.x[cur] - p[m].x[cur])) tmp = min(tmp, query(lson));
53     }
54     return min(res, tmp);
55 }
56 void solve() {
57     int n; scanf("%d",&n); 
58     for (int i=1; i<=n; ++i) {
59         for (int j=0; j<DIM; ++j) 
60             scanf("%lld",&ori[i].x[j]);
61         p[i] = ori[i];
62     }
63     build(Root);
64     for (int i=1; i<=n; ++i) {
65         Q = ori[i];
66         printf("%lld
", query(Root));
67     }
68 }
69 int main() {
70     int Case;scanf("%d",&Case);
71     while (Case--) solve();
72     return 0;
73 }