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.

#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;
}