Wireless Network

题意

在一个网络中的共N台电脑都已经坏了，知道这些电脑的直角坐标，现在维修员对网络中的电脑一个一个维修，一边维修一边问某两台电脑是否可以通信了，通信双方电脑必须是已经修好了的，并且通信路线上每两台电脑的直接距离不能超过D。你需要回答维修员的问题。

分析

此题算是很典型的并查集算法，每次维修好一台电脑就把此台电脑和与其距离小于等于D的电脑合并在一起，也就是用并查集的join操作，然后师傅问两台电脑是否修好，就用find操作，就可以了。

AC 代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;
int N,D;
const int maxn = 1e3+10;
struct node{
    ll x,y;
    bool ok;//是否已经维修好
}no[1010];
int fa[maxn];
void init(){
    for(int i = 1;i<=N;i++) fa[i] = i;
}
int find(int x){
    if(x != fa[x])
        return fa[x] = find(fa[x]);
    return fa[x];
}
void join(int x,int y){
    int fx = find(x),fy =find(y);
    if(fx!=fy) fa[fx] = fy;
}
bool dis(int a,int b){
    if(!no[a].ok || !no[b].ok) return false;
    return (no[a].x-no[b].x)*(no[a].x-no[b].x) + (no[a].y-no[b].y)*(no[a].y-no[b].y) <= D*D;
}
int main(){
    cin>>N>>D;
    init();
    ll x,y;
    for(int i = 1;i<=N;i++){
        scanf("%lld %lld",&x,&y);
        no[i] = {x,y,false};
    }
    char op[2];int id1,id2;
    while(~scanf("%s",op)){
        if(*op == 'O'){
            scanf("%d",&id1);
            if(no[id1].ok) continue;//如果已经修好了，就不用修了
            no[id1].ok = true;
            for(int i = 1;i<=N;i++){
                if(i!=id1 && dis(i,id1))
                    join(i,id1);
            }
        }else{
            scanf("%d%d",&id1,&id2);
            if(find(id1) != find(id2))
                puts("FAIL");
            else
                puts("SUCCESS");
        }
    }

    return 0;
}