Problem G - Monitoring the Amazon

Time Limit: 5 seconds

Memory Limit: 1 Mb

Background

A network of autonomous, battery-powered, data acquisition stations has been installed to monitor the climate in the region of Amazon. An order-dispatch station can initiate transmission of instructions to the control stations so that they change their current parameters. To avoid overloading the battery, each station (including the order-dispatch station) can only transmit to two other stations. The destinataries of a station are the two closest stations. In case of draw, the first criterion is to chose the westernmost (leftmost on the map), and the second criterion is to chose the southernmost (lowest on the map).

The Problem

You are commissioned by Amazon State Government to write a program that decides if, given the localization of each station, messages can reach all stations.

Input

The input consists of an integer N, followed by N pairs of integers Xi, Yi, indicating the localization coordinates of each station. The first pair of coordinates determines the position of the order-dispatch station, while the remaining N-1 pairs are the coordinates of the other stations. The following constraints are imposed: -20 ≤ Xi, Yi ≤ 20, and 1 ≤ N ≤ 1000. The input is terminated with N = 0.

Output

For each given expression, the output will echo a line with the indicating if all stations can be reached or not (see sample output for the exact format).

Sample input

4
1 0 0 1 -1 0 0 -1
8
1 0 1 1 0 1 -1 1 -1 0 -1 -1 0 -1 1 -1
6
0 3 0 4 1 3 -1 3 -1 -4 -2 -5
0

Sample output

All stations are reachable.
All stations are reachable.
There are stations that are unreachable.

---

題目描述：

平面上有 n 個點，每個點只會連接到最近的那個點，
如果距離最近的有一樣的點，那麼取左下角的點(x 座標越小越好，y 座標越小越好)

因此 n 個點，會有 n 個邊，要碼是環不然就是樹、再不然就是有一個環的樹。

其實就是問這張圖是不是一個 component。

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Pt {
    int x, y;
    bool operator<(const Pt &a) const {
        if(x != a.x)
            return x < a.x;
        return y < a.y;
    }
};
struct E {
    int x, y, v, idx;
    E(int a, int b, int c, int d):
        x(a), y(b), v(c), idx(d) {}
    bool operator<(const E &a) const {
        if(v != a.v)
            return v < a.v;
        if(x < a.x)
            return x < a.x;
        return y < a.y;
    }
};
int p[1005], rank[1005];
int findp(int x) {
    return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] >= rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}

int main() {
    int n, i, j, k;
    Pt D[1005];
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++)
            scanf("%d %d", &D[i].x, &D[i].y);
        for(i = 0; i < n; i++)
            p[i] = i, rank[i] = 1;
        sort(D, D+n);
        int component = n;
        E oo(0,0,0xfffffff, 0), tmp(0,0,0,0);
        for(i = 0; i < n; i++) {
            E e = oo;
            for(j = i+1; j < n; j++) {
                if((D[j].x-D[i].x)*(D[j].x-D[i].x) > e.v)
                    break;
                tmp = E(D[j].x, D[j].y, (D[i].x-D[j].x)*(D[i].x-D[j].x)+(D[i].y-D[j].y)*(D[i].y-D[j].y), j);
                if(tmp < e)
                    e = tmp;
            }
            for(j = i-1; j >= 0; j--) {
                if((D[i].x-D[j].x)*(D[i].x-D[j].x) > e.v)
                    break;
                tmp = E(D[j].x, D[j].y, (D[i].x-D[j].x)*(D[i].x-D[j].x)+(D[i].y-D[j].y)*(D[i].y-D[j].y), j);
                if(tmp < e)
                    e = tmp;
            }
            component -= joint(i, e.idx);
            if(component > n-i)
                break;
        }
        if(component == 1)
            puts("All stations are reachable.");
        else
            puts("There are stations that are unreachable.");
    }
    return 0;
}