Wireless Network(POJ 2236)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <set>
 6 #include <cmath>
 7 using namespace std;
 8 #define Max 1005
 9 int n,d;
10 int per[Max];
11 bool vis[Max];
12 struct point
13 {
14     int x,y;    
15 }e[1002];
16 void init()
17 {
18     for(int i=0;i<=n;i++)
19         per[i]=i;
20     return;
21 }
22 int find(int x)
23 {
24     if(x==per[x])
25         return x;
26     int tem,root=x,t=x;
27     while(root!=per[root])    root=per[root];
28     while(t!=per[t])
29     {
30         tem=per[t];
31         per[t]=root;
32         t=tem;
33     }
34 }
35 bool dis(int q,int p)
36 {
37     point a=e[q],b=e[p];
38     int f=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
39     return d*d>=f;
40 }
41 int unite(int a,int b)
42 {
43     a=find(a);
44     b=find(b);
45     if(a!=b)
46         per[a]=b;
47     return 0;
48 }
49 int main()
50 {
51     int i,j;
52     int v,u,p;
53     char ch;
54     freopen("in.txt","r",stdin);
55     scanf("%d%d",&n,&d);
56     init();
57     memset(vis,0,sizeof(vis));
58     for(i=1;i<=n;i++)
59         scanf("%d%d",&e[i].x,&e[i].y);
60     getchar();
61     while(scanf("%c",&ch)!=EOF)
62     {
63         if(ch==‘S‘)
64         {
65             scanf("%d%d",&u,&v);
66             if(find(u)==find(v))
67                 printf("SUCCESS\n");
68             else
69                 printf("FAIL\n");
70         }
71         else if(ch==‘O‘)
72         {
73             scanf("%d",&u);
74             vis[u]=1;
75             for(i=1;i<=n;i++)
76                 if(vis[i]&&i!=u&&dis(i,u))
77                     unite(u,i);
78         }
79         getchar();
80     }
81     return 0;
82 }