Wireless Network

描述

An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftershock （预余震）attacked, all computers in the network were all broken. The computers are repaired one by one, and the network gradually began to work again. Because of the hardware restricts, each computer can only directly communicate with the computers that are not farther than d meters from it. But every computer can be regarded as the intermediary（中介） of the communication between two other computers, that is to say computer A and computer B can communicate if computer A and computer B can communicate directly or there is a computer C that can communicate with both A and B.

In the process of repairing the network, workers can take two kinds of operations at every moment, repairing a computer, or testing if two computers can communicate. Your job is to answer all the testing operations.

输入

There are multiple test cases. The first line contains two integers N and d (1 <= N <= 1001, 0 <= d <= 20000). Here N is the number of computers, which are numbered from 1 to N, and D is the maximum distance two computers can communicate directly. In the next N lines, each contains two integers xi, yi (0 <= xi, yi <= 10000), which is the coordinate of N computers. From the (N+1)-th line to the end of input, there are operations, which are carried out one by one. Each line contains an operation in one of following two formats:

1. "R p" (1 <= p <= N), which means repairing computer p.

2. "S p q" (1 <= p, q <= N), which means testing whether computer p and q can communicate.

3. "Q", which means quiting all the testing operations of each test case.

The input will not exceed 300000 lines.

输出

For each Testing operation, print "SUCCESS" if the two computers can communicate, or "FAIL" if not.

样例输入

4 1
0 1
0 2
0 3
0 4
R 1
R 2
R 4
S 1 4
R 3
S 1 4
Q

样例输出

FAIL
SUCCESS

提示

POJ 2236

思路

• 对于R p操作，将指定编号的电脑p标记为已修复，并检查它与网络中其他已修复电脑的距离，如果距离在d以内，则将它们合并。

• 对于S p q操作，检查电脑p和q是否能够通信（即它们是否有相同的根节点），并输出相应的结果。

code

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
typedef long long ll;
#define D(x1,x2) (x1-x2)*(x1-x2)
int pre[maxn];
struct Station {
	ll x, y;
	int work;//1代表已维修好，可以工作
}station[maxn];

void init() {
	for (int i = 1; i < maxn; i++) {
		pre[i] = i;
	}
}
int find(int x) {
	return pre[x] == x ? x : pre[x] = find(pre[x]);
}
void merge(int x, int y) {
	int rootx = find(x);
	int rooty = find(y);
	if (rootx != rooty) {
		pre[rootx] = rooty;
	}

}

int main()
{
	ll n, d;
	while (scanf("%lld%lld",&n,&d)!=EOF) {//n为电脑数,d为通信最小距离
		for (int i = 1; i <= n; i++) {
			scanf("%d%d",&station[i].x,&station[i].y);
			station[i].work = 0;
		}
		char cz[2];
		init();
		while (scanf("%s", cz) != EOF) {
			if(cz[0] == 'Q') break;
			if (cz[0] == 'R') {//维修
				int p;
				scanf("%d", &p);
				station[p].work = 1;
				for (int i = 1; i <= n; i++) {
				ll deltx = D(station[i].x , station[p].x);
				ll delty = D(station[i].y , station[p].y);
					if (i!=p && station[i].work == 1 && (deltx + delty <= d * d)) {
						merge(p, i);
					}
				}
			}
			else {
				int p, q;
				scanf("%d%d", &p,&q);
					if (find(p) == find(q) ) {
						printf("SUCCESS\n");
					}
					else {
						printf("FAIL\n");
					}
			}
		}
	}
	return 0;
}