POJ 2246 Wireless Network【そして基礎問題を調べる】

POJ 2246 Wireless Network

タイトルリンク:vjudge転送ゲート
N個の壊れたコンピュータと座標を与えて、通信距離をLにすることを規定して、各コンピュータに対して2つの操作を行って、修理あるいは2つのコンピュータが通信することができるかどうかをテストして、いくつかの操作を与えて、その中のテストの操作が成功するかどうかを判断します
具体的な考え方:O操作については、1つのパソコンを修理するごとに、そのパソコンとすべての検査されたパソコンとの間で通信できるかどうかを検査し、2つのパソコンを同じ集合の中に入れてS操作を行い、2台のパソコンが修理されたかどうかを判断し、同じ集合の中で、SUCCESSをいっぱい出力し、そうでなければFAILを出力する.
具体的なコード:

#include
#include
#include
#include
using namespace std;
int const N = 1005;
double const eps = 1e-5;
int fa[N];
int visit[N], cnt = 0;	// 
int beenOp[N];	// 
int n, L;
struct Node {
     
	int x, y;
}point[N];
void init()
{
     
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}
int find(int i)
{
     
	if (i != fa[i])
		fa[i] = find(fa[i]);
	return fa[i];
}
void unite(int i, int j)
{
     
	int x = find(i);
	int y = find(j);
	if (x == y)return;
	fa[x] = y;
}
bool cmpDis(int a, int b)	// 
{
     
	double len = sqrt((double)((point[a].x - point[b].x)*(point[a].x - point[b].x) + (point[a].y - point[b].y)*(point[a].y - point[b].y)));
	if (len - L<=eps)return true;
	return false;
}
int main()
{
     
	memset(beenOp, 0, sizeof(beenOp));
	scanf("%d%d", &n, &L);
	init();
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &point[i].x, &point[i].y);
	getchar();
	char c;
	while (~scanf("%c ", &c))
	{
     
		if (c == 'O') {
     
			int opt;
			scanf("%d", &opt);
			for (int i = 0; i < cnt; i++) {
     
				if (cmpDis(visit[i], opt)) {
     
					unite(visit[i], opt);
				}
			}
			visit[cnt++] = opt;
			beenOp[opt] = 1;
		}
		else {
     
			int a, b;
			scanf("%d%d", &a, &b);
			if (beenOp[a] && beenOp[b] && find(a) == find(b)) {
     
				printf("SUCCESS
");
			}
			else printf("FAIL
");
		}
		getchar();
	}
	return 0;
}