POJ 2236 Wireless Network

Description

n台坏掉的电脑（1~N），一个限制距离d

n个坐标（1~N），两种操作（O x 表示修复第x台电脑）（S x y表示询问：第x与第y台电脑能否直接或间接相连）

题目链接 http://poj.org/problem?id=2236

并查集

不过用 while(ch = getchar()) 超时，用while(cin >> ch)就过，前者读不到EOF？

Code

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const double eps = 1e-6;

int n, d;
int pre[1005];
bool vis[1005];///修没修
int x[1005];
int y[1005];

void init()///初始化顶级是自身
{
    for(int i = 0; i <= n; ++i)
        pre[i] = i;
}

int found(int x)
{
    if(x != pre[x])
        pre[x] = found(pre[x]);///路径压缩
    return pre[x];
}

void unite(int a, int b)
{
    int x = found(a);
    int y = found(b);
    if(x != y)
        pre[y] = x;
    return ;
}

bool check(int a, int b)
{
    if((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]) <= d * d)
        return 1;
    return 0;
}

int main()
{
    ///全局处的n我又在主函数里定义了！！！
    scanf("%d%d", &n, &d);
    init();///勿忘在主函数里调用(而且是在n输入后调用！！！)
    for(int i = 1; i <= n; ++i)
        scanf("%d%d", &x[i], &y[i]);
    getchar();///涉及字符输入注意吃回车
    char ch;
    vector<int> vec;
//    while(ch = getchar())
    while(cin >> ch)
    {
        if(ch == 'O')
        {
            int tem;
            scanf("%d", &tem);
            getchar();
            vis[tem] = 1;
            for(int i = 1; i <= n; ++i)
                if(vis[i] && i != tem && check(i, tem))
                    unite(i, tem);///tem与所有修好的点联合一遍
        }
        else if(ch == 'S')
        {
            int there, here;
            scanf("%d%d", &there, &here);
            getchar();
            int p = found(there);
            int q = found(here);
            if(p == q)
                cout << "SUCCESS" << '\n';
            else
                cout << "FAIL" << '\n';
        }
    }
    return 0;
}