POJ2236 Wireless Network

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1005;
struct node {
    int x, y, id;
};
int gn, gd;
//Accepted	752K	3094MS	G++	2061B	2014-03-18 17:05:40
int getFather(int x);
double getDistance(node a, node b);
void Union(int x, int y);

vector<node> inform;
vector<node> connected;
int f[N+10];

int main()
{
    node tmp;
    inform.clear(); connected.clear();
    inform.push_back(tmp);//index = 0; unused.
    scanf("%d%d", &gn, &gd);
    for(int i = 1; i <= gn; i++) {
        scanf("%d%d", &tmp.x, &tmp.y);
        tmp.id = i;
        inform.push_back(tmp);
    }
    getchar();
    for(int i = 0; i < N; i++) f[i] = i;
    char ch;
    int pos, p, q;
    while(scanf("%c", &ch) != EOF) {
        if(ch == ‘O‘) {
            scanf("%d", &pos);
            getchar();
            node now = inform[pos];
            for(int i = 0; i < (int)connected.size(); i++) {
                double dis = getDistance(now, connected[i]);
                if(dis <= gd) {
                    Union(connected[i].id, pos);
                }
            }
            connected.push_back(now);
        } else {
            scanf("%d%d", &p, &q);
            getchar();
            int p1 = getFather(p);
            int p2 = getFather(q);
            if(p1==p2) printf("SUCCESS\n");
            else printf("FAIL\n");
        }
    }
    return 0;
}
int getFather(int x) {
    if(x == f[x]) return x;
    else return f[x] = getFather(f[x]);
}
double getDistance(node a, node b) {
    double t1 = (a.x-b.x)*(a.x-b.x);
    double t2 = (a.y-b.y)*(a.y-b.y);
    return sqrt((t1+t2)*1.0);
}
void Union(int x, int y) {
    int p1 = getFather(x);
    int p2 = getFather(y);
    if(p1 != p2) f[p1] = p2;
}

POJ2236 Wireless Network,古老的榕树,5-wow.com