papamelon 348. 修复网络 Wireless Network（挑战程序设计竞赛）

地址 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;
}

视频题解空间