2236:Wireless Network

keyword

Union-FInd　C++

概要

2次元平面上の点がN(<1000)個与えられる。どの点も最初はinvalidな状態である。validな2点は距離がd以下であるとき隣接する。ある点がvalidになったという情報と、点i,jが連結しているかどうかを尋ねるクエリが与えられる。クエリに対してyesかnoを出力する問題。
UnionFindでくっつけていくだけ。ちょっと無駄が多い感じはする。

int p[1002];

int getRoot(int x){
    if(x==p[x]) return x;
    return p[x] = getRoot(p[x]);
}

bool isSame(int x, int y){
    return getRoot(x) == getRoot(y);
}

void merge(int x, int y){
    p[getRoot(x)] = getRoot(y);
}

inline int sq(int x){ return x*x;}

inline int getDist(int x1, int y1, int x2, int y2){
    return sq(x1-x2) + sq(y1-y2);
}

int main(){
    int n, d, i, j, pos, tar, x, y;
    char c;
    char line[20];
    int xs[1002], ys[1002], adj[1002][1002];
    scanf("%d%d\n",&n,&d);
    d = d*d;

    REPONE(i,n){
        scanf("%d%d\n",xs+i,ys+i);
    }

    REPONE(i,n) p[i] = 0;

    REPONE(i,n){
        pos = 0;
        REPONE(j,n)if(i!=j && d >= getDist(xs[i],ys[i],xs[j],ys[j])){
            adj[i][pos++] = j;
        }
        adj[i][pos] = 0;
    }

    while(scanf("%c",&c)!=EOF){
        if(c=='O'){
            scanf("%d\n",&tar);
            p[tar] = tar;
            for(i=0;adj[tar][i];i++)if(p[adj[tar][i]])
                merge(adj[tar][i],tar);
        }
        else{
            scanf("%d%d\n",&x,&y);
            if(p[x] && p[y] && isSame(x,y)) printf("SUCCESS\n");
            else printf("FAIL\n");
        }
    }

    return 0;
}