地址 https://www.papamelon.com/problem/348
给定 N 台电脑，它们分别落在地图上的坐标 xi,yi上。
现在它们都损坏了。我们准备修复其中的某一些电脑。
当一台电脑修复好了后，它和其他相距不超过距离 d 的正常电脑就可以通信。
通信具有传递性：A 和 B 能通信，
B 和 C 能通信，那么
A 和 C 就能通信。
现在给定两种操作：
O p：1≤p≤N，表示修复第 p 台电脑
S p q：
1≤p,q≤N，测试 ,
p,q 两台电脑是否能通信
两种操作随机给出，对于每个 S 操作，输出 SUCCESS 或 FAIL，代表是否能通信。
输入
第一行两个整数
N(1≤N≤1001),d(0≤d≤20000)
接下来 N 行，每行是一台电脑的坐标
接下来若干行，是随机给出的操作，以 EOF 结束，操作的输入格式如上所述
样例 1
输入
4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4
输出
FAIL
SUCCESS
并查集
每修好一台电脑 与周边电脑计算坐标 如果在范围内，合并两台电脑的编号。
注意判断记录 可以不使用开根号计算。
#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
pair<int, int> axis[N];
int repair[N];
void init() {
for (int i = 0; i < N; i++) {
f[i] = i;
}
}
int find(int x) {
if (f[x] != x) {
f[x] = find(f[x]);
}
return f[x];
}
void merge(int a, int b) {
f[find(a)] = find(b);
}
int calcDis(int a, int b) {
int res = (axis[a].first - axis[b].first) * (axis[a].first - axis[b].first) +
(axis[a].second - axis[b].second) * (axis[a].second - axis[b].second);
return res;
}
int n, d;
int main() {
init();
cin >> n >> d;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
axis[i] = { x,y };
}
string op;
while (cin >> op) {
if (op == "O") {
int t;
cin >> t;
repair[t] = 1;
for (int i = 1; i <= n; i++) {
if (find(i) == find(t)) continue;
if (repair[i]==1 && calcDis(i, t) <= ((long long)1 * d * d) ) {
merge(i, t);
}
}
}
else {
int a, b; cin >> a >> b;
if (find(a) == find(b)) {
cout << "SUCCESS" << endl;
}
else {
cout << "FAIL" << endl;
}
}
}
return 0;
}