http://acm.hdu.edu.cn/showproblem.php?pid=2966題目的意思是：平面上有n個點（n<100000），求每個點的最近點到該點的平方距離。 KD_Tree可以解決此題。詳細資料可以參看此鏈接 http://en.wikipedia.org/wiki/Kd-tree，上面給出了算法。 PS: 這道題時限開了恐怖的30秒。
  hdu_2966
1 #include <cstdio>
2#include <iostream>
3#include <algorithm>
4#include <cmath>
5#include <cstring>
6using namespace std;
7typedef __int64 ll;
8const ll inf = 4611686018427387904LL;
9const int maxn = 100050;
10
11struct point
12 {
13 int x, y;
14 }p[maxn], pp[maxn];
15
16bool cmp1( const point & a, const point & b ) { return a.x < b.x; }
17bool cmp2( const point & a, const point & b ) { return a.y < b.y; }
18
19struct node
20{
21 int axis;
22 point mid;
23 node *ch[2]; // 0 left, 1 right
24}tree[maxn];
25int len;
26ll ans;
27
28node * NewNode( )
29{
30 tree[len].ch[0] = tree[len].ch[1] = NULL;
31 return & tree[len++];
32}
33
34node * make_tree( int l, int r, int dep )
35{
36 if( l > r ) return NULL;
37 node * q = NewNode( );
38 int t = dep % 2;
39 q -> axis = t;
40  if( l == r ) { q -> mid = p[l]; return q; }
41
42 if( t == 0 ) sort( p + l, p + r + 1, cmp1 ); // X - axis
43 else sort( p + l, p + r + 1, cmp2 ); // Y - axis
44
45 int mid = ( l + r ) >> 1;
46 q -> mid = p[mid];
47
48 q -> ch[0] = make_tree( l, mid - 1, dep + 1 );
49 q -> ch[1] = make_tree( mid + 1, r, dep + 1 );
50 return q;
51}
52
53ll dis( point a, point b )
54{
55 ll x = a.x - b.x;
56 ll y = a.y - b.y;
57 return x * x + y * y;
58}
59
60void search_nearpoint( node * q, const point & a )
61{
62 // 首先找到葉結點
63 if( q == NULL ) return;
64
65 int tmp, s;
66 if( q -> axis == 0 ) tmp = q -> mid.x, s = a.x; // X - axis
67 else tmp = q -> mid.y, s = a.y; // Y - axis
68
69 if( s <= tmp ) search_nearpoint( q -> ch[0], a ); // leftson
70 else search_nearpoint( q -> ch[1], a ); // rightson
71
72 ll d = dis( q -> mid, a );
73 if( d && d < ans ) ans = d;
74
75 if( (ll)( tmp - s ) * ( tmp - s ) < ans ) // 查找另一半平面
76 {
77 if( s <= tmp )search_nearpoint( q -> ch[1], a );
78 else search_nearpoint( q -> ch[0], a );
79 }
80}
81
82int main(int argc, char *argv[])
83{
84 node * root;
85 int cas, n, x, y;
86 scanf("%d",&cas);
87 while( cas-- )
88 {
89 scanf("%d",&n);
90 for( int i = 0; i < n; i++ )
91 {
92 scanf("%d%d",&p[i].x,&p[i].y);
93 pp[i] = p[i];
94 }
95 len = 0;
96 root = make_tree( 0, n - 1, 0 );
97 for( int i = 0; i < n; i++ )
98 {
99 ans = inf;
100 search_nearpoint( root, pp[i] );
101 printf("%I64d\n",ans);
102 }
103 }
104 return 0;
105}
106
|