POJ 2236 Wireless Network

http://poj.org/problem?id=2236
并查集
预处理每两台之间的距离这样不用再后面重复计算
用一个数组dist[i][j]存储
修好一台就枚举N 合并集合
 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 struct Computer
 7 {
 8     int x, y;
 9     bool repair;
10 }computer[1007];
11 
12 bool near[1007][1007]; //预处理 两台电脑之间 距离的关系
13 int par[1007];
14 
15 int get_dist(int a, int b)
16 {
17     if (a == b) return 0;
18     return (computer[a].x - computer[b].x)*(computer[a].x - computer[b].x)+(computer[a].y - computer[b].y)*(computer[a].y - computer[b].y);
19 }
20 int find(int x)
21 {
22     if (par[x] == x) return x;
23     else return par[x] = find(par[x]);
24 }
25 
26 void unite(int x, int y)
27 {
28     int px = find(x), py = find(y);
29     if (px == py) return ;
30     else par[py] = px;
31 }
32 
33 bool same(int x, int y)
34 {
35     int px = find(x), py = find(y);
36     return px == py;
37 }
38 
39 
40 int main()
41 {
42     freopen("in.txt", "r", stdin);
43     int N;
44     int D;
45     scanf("%d%d", &N, &D);
46     D*=D;//变成D^2
47     memset(near, 0, sizeof(near));
48     for (int i = 1; i <= N; i++)
49     {
50         int x, y;
51         par[i] = i;
52         scanf("%d%d",&x, &y);
53         computer[i].y = y;
54         computer[i].repair = false;
55     }
56     for (int i = 1; i <= N; i++)
57     {
58         for (int j = 1; j <= N; j++)
59         {
60             if (get_dist(i, j) <= D )
61             {
62                 near[i][j] = 1;
63                 near[j][i] = 1;
64             }
65         }
66     }
67     char ch;
68     getchar();
69     while (~scanf("%c", &ch))
70     {
71         int c1, c2;
72         if (ch == 'O')
73         {
74             scanf("%d", &c1);
75             computer[c1].repair = true;
76             for (int i = 1; i<= N; i++)
77             {
78                 if (near[i][c1] && computer[i].repair) unite(c1, i);
79             }
80             getchar();
81 
82         }
83         else
84         {
85             scanf("%d%d", &c1, &c2);
86             getchar();
87             if (computer[c1].repair && computer[c2].repair && same(c1, c2)) printf("SUCCESS
");//必须要都修好了
88             else printf("FAIL
");
89         }
90     }
91     return 0;
92 }