Poj 2236: Wireless Network

poj2236.md

Poj 2236: Wireless Network

題目

分析

並查集基本題，直接看程式碼

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

struct Point {
    int x, y;
    bool fixed;
};

int N, D;
Point points[1002];

int par[1002];
int ran[1002];

void ds_init() {
    for (int i = 0; i < N; i++) {
        par[i] = i;
        ran[i] = 0;
    }
}

int ds_find(int a) {
    if (par[a] == a)
        return a;
    return (par[a] = ds_find(par[a]));
}

void ds_unite(int a, int b) {
    a = ds_find(a);
    b = ds_find(b);
    if (a == b)
        return;

    if (ran[a] < ran[b]) {
        par[a] = b;
    }
    else {
        par[b] = a;
        if (ran[a] == ran[b])
            ran[a]++;
    }
}

bool ds_same(int a, int b) {
    return ds_find(a) == ds_find(b);
}


bool connect(Point& p1, Point& p2) {
    int dx = p1.x - p2.x;
    int dy = p1.y - p2.y;
    return dx * dx + dy * dy <= D * D;
}

int main() {
    scanf("%d %d", &N, &D);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &points[i].x, &points[i].y);
        points[i].fixed = false;
    }

    ds_init();

    getchar();
    char query;
    while (scanf("%c", &query) != EOF) {
        if (query == 'O') {
            int p;
            scanf("%d\n", &p);
            p--;

            points[p].fixed = true;

            for (int i = 0; i < N; i++)
                if (i != p && points[i].fixed && connect(points[p], points[i]))
                    ds_unite(p, i);
        }
        else {
            int p, q;
            scanf("%d %d\n", &p, &q);
            p--; q--;

            if (ds_same(p, q))
                puts("SUCCESS");
            else
                puts("FAIL");
        }
    }
    return 0;
}