poj 2236 Wireless Network

思路：
并查集。
实现：
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cmath>
  4 using namespace std;
  5 
  6 struct node
  7 {
  8     int x, y;
  9 };
 10 node a[1005];
 11 char t;
 12 int n, p, q;
 13 double d;
 14 int ran[1005];
 15 int par[1005];
 16 bool ok[1005];
 17 
 18 double dis[1005][1005];
 19 
 20 double square(int a)
 21 {
 22     return a * a;
 23 }
 24 
 25 void init()
 26 {
 27     for (int i = 1; i <= n; i++)
 28     {
 29         for (int j = 1; j <= n; j++)
 30         {
 31             dis[i][j] = sqrt(square(a[i].x - a[j].x) + square(a[i].y - a[j].y));
 32         }
 33         par[i] = i;
 34         ran[i] = 0;
 35     }
 36 }
 37 
 38 int find(int x)
 39 {
 40     if (par[x] == x)
 41         return x;
 42     return par[x] = find(par[x]);
 43 }
 44 
 45 void unite(int x, int y)
 46 {
 47     x = find(x);
 48     y = find(y);
 49     if (x == y)
 50         return;
 51     if (ran[x] < ran[y])
 52     {
 53         par[x] = y;
 54     }
 55     else
 56     {
 57         par[y] = x;
 58         if (ran[x] == ran[y])
 59         {
 60             ran[x]++;
 61         }
 62     }
 63 }
 64 
 65 bool same(int x, int y)
 66 {
 67     return find(x) == find(y);
 68 }
 69 
 70 int main()
 71 {
 72     scanf("%d %lf", &n, &d);
 73     for (int i = 1; i <= n; i++)
 74     {
 75         scanf("%d %d", &a[i].x, &a[i].y);
 76     }
 77     getchar();
 78     init();
 79     while (scanf("%c", &t) != EOF)
 80     {
 81         if (t == 'O')
 82         {
 83             scanf("%d", &p);
 84             getchar();
 85             for (int j = 1; j <= n; j++)
 86             {
 87                 if (dis[p][j] <= d && ok[j])
 88                 {
 89                     unite(p, j);
 90                 }
 91             }
 92             ok[p] = true;
 93         }
 94         else
 95         {
 96             scanf("%d %d", &p, &q);
 97             getchar();
 98             if (same(p, q))
 99                 puts("SUCCESS");
100             else
101                 puts("FAIL");
102         }
103     }
104     return 0;
105 }