POJ2236.cpp

#include <iostream>
#include <cstdio>
#include <cmath>
typedef long long ll;
ll x[1002], y[1002];
bool machine[1002] = {false};
int par[1002];
int rank[1002];
void init(int n){
	for(int i = 0; i < n; ++i){
		par[i] = i;
		rank[i] = 0;
	}
}
int find(int x){
	if(par[x] == x){
		return x;
	}else {
		return par[x] = find(par[x]);
	}
}
void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y)return ;
	if(rank[x] < rank[y]){
		par[x] = y;
	}else{
		par[y] = x;
		if(rank[x] == rank[y])rank[x]++;
	}
}
bool same(int x, int y){
	return find(x) == find(y);
}
int main(){
	ll N, d;
	scanf("%d %lld",&N, &d);
	for(int i = 0; i < N; ++i){
		scanf("%lld %lld", &x[i], &y[i]);
	}
	for(int i = 0; i < 1002; ++i)machine[i] = false;
	init(N);
	char qry[16];
	while(fgets( qry, 16, stdin ) != NULL){
		if(qry[0] == 'O'){
			int p;
			sscanf(qry, "O %d", &p);
			p--;
			machine[p] = true;
			//par[p]=p;
			for(int i = 0; i < N; ++i){
				if(i == p)continue;
				if(!machine[i])continue;
				ll disx = (x[i] - x[p]), disy = (y[i] - y[p]);
				if(disx * disx + disy * disy <= d * d && !same(i,p))unite(i, p);
			}
		}else if(qry[0] == 'S'){
			int p, q;
			sscanf(qry, "S %d %d", &p, &q);
			p--, q--;
			//int disx = (x[p] - x[q]), disy = (y[p] - y[q]);
			if(same(p, q) && machine[p] && machine[q])printf("SUCCESS\n");
			else printf("FAIL\n");
		}
	}
}