poj2236

简单并查集

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;

#define maxn 1005
#define eps 1.0e-8

struct Computer
{
    int x, y;
    bool r;
}computer[maxn];
int n, d;
int father[maxn];

int getanc(int a)
{
    if (father[a] == a)
        return a;
    return father[a] = getanc(father[a]);
}

void merge(int a, int b)
{
    father[getanc(a)] = getanc(b);
}

double dis(Computer &a, Computer &b)
{
    return sqrt((a.x - b.x) *(a.x - b.x) +(a.y - b.y) *(a.y - b.y));
}

void make(int a)
{
    computer[a].r = true;
    for (int i = 0; i < n; i++)
        if (computer[i].r && dis(computer[i], computer[a]) < d + eps)
            merge(i, a);
}

int main()
{
    //freopen("t.txt", "r", stdin);
    scanf("%d%d", &n, &d);
    for (int i = 0; i < n; i++)
    {
        father[i] = i;
        scanf("%d%d", &computer[i].x, &computer[i].y);
        computer[i].r = false;
    }
    getchar();
    char ch;
    int a, b;
    while (scanf("%c", &ch) != EOF)
    {
        if (ch == 'O')
        {
            scanf("%d", &a);
            a--;
            getchar();
            make(a);
        }else
        {
            scanf("%d%d", &a, &b);
            a--;
            b--;
            getchar();
            if (getanc(a) == getanc(b))
                printf("SUCCESS\n");
            else
                printf("FAIL\n");
        }
    }
    return 0;
}