Wireless Network POJ

 1 #include<iostream>
 2 #include<vector>
 3 #include<string>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstdio>
 7 #include<cstring>
 8 
 9 using namespace std;
10 
11 int n, d;
12 double dis[1010][1010];
13 struct Point
14 {
15     double x, y;
16 }cur[1010];
17 
18 int Tree[1010];
19 
20 int findRoot(int x)
21 {
22     if(Tree[x] == -1)
23         return x;
24     int tmp = findRoot(Tree[x]);
25     Tree[x] = tmp;
26     return tmp;
27 }
28 
29 int main()
30 {
31     scanf("%d %d", &n, &d);
32     for(int i = 1; i <= n; ++i)
33     {
34         Tree[i] = -1;
35         double x, y;
36         scanf("%lf %lf", &x, &y);
37         cur[i].x = x;
38         cur[i].y = y;        
39     }
40     
41     for(int i = 1; i <= n; ++i)
42         for(int j = i; j <= n; ++j)
43         {
44             dis[i][j] = dis[j][i] = sqrt((cur[i].x - cur[j].x)*(cur[i].x - cur[j].x)+(cur[i].y - cur[j].y)*(cur[i].y - cur[j].y)); 
45         }
46     
47     vector<int> rep;    // repaired
48     char c;
49     while(scanf("%c", &c) != EOF)
50     {
51         if(c == 'O')
52         {
53             int t;
54             scanf("%d", &t);
55             for(int i = 0; i < rep.size(); ++i)
56             {
57                 if(dis[rep[i]][t] <= d)
58                 {
59                     /* 不能这样写，否则会导致并查集的树结构不好，
60                        路径压缩次数过多，导致RuntimeError(栈溢出) 
61                     int ri = findRoot(rep[i]);
62                     Tree[ri] = t;
63                     */
64                     
65                     // 标准写法 
66                     int ri = findRoot(rep[i]);
67                     int rt = findRoot(t);
68                     if(ri != rt)
69                         Tree[ri] = rt;
70                 
71                 } 
72             }
73             rep.push_back(t);
74             
75         }
76         else if(c == 'S')
77         {
78             int t1, t2;
79             scanf("%d %d", &t1, &t2);
80             int rt1 = findRoot(t1);
81             int rt2 = findRoot(t2);
82             if(rt1 == rt2)
83                 printf("SUCCESS
");
84             else
85                 printf("FAIL
");
86         }
87     }
88     
89     return 0;
90 }