POJ 2236 Wireless Network 几何+并查集

Description

Input

Output

Sample Input

4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4

Sample Output

FAIL
SUCCESS

Source

//4340K	3079MS
#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 1007
char s[5];
int x[M],y[M],pre[M],vis[M],g[M][M];
int n,d;
void init()
{
    memset(g,0,sizeof(g));
    for(int i=1;i<=n;i++)
    {
        pre[i]=i;
        vis[i]=0;
    }
        
}
int find(int x)
{
    while(x!=pre[x])
        x=pre[x];
    return x;
}
bool judge(int i,int j)
{
    return ((y[j]-y[i])*(y[j]-y[i])+(x[j]-x[i])*(x[j]-x[i]))<=d*d;
}
int main()
{
    scanf("%d%d",&n,&d);
    init();
    int a,b,c;
    for(int i=1;i<=n;i++)
        scanf("%d%d",&x[i],&y[i]);
    while(scanf("%s",s)!=EOF)
    {
        if(s[0]==‘O‘)
        {
            scanf("%d",&c);
            vis[c]=1;
            for(int i=1;i<=n;i++)
            {
                if(i==c)continue;
                if(judge(c,i)&&vis[i])
                {
                    int xx=find(c);
                    int yy=find(i);
                    pre[xx]=yy;
                }
            }
        }
        if(s[0]==‘S‘)
        {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b))printf("SUCCESS\n");
            else printf("FAIL\n");
        }
    }
    return 0;
}