UVa 10687

Summary

Each vertex (station) is connected to two vertices - its two closest neighbors, with some tiebreaking rules. Construct the graph, and check if the resultant graph is connected.

Explanation

Construct the graph, and use any of the Graph Connectivity algorithms. Since V is at most 1000, ${\displaystyle O(V^{2})}$ implementation will do.

Gotcha's

• Remember the tiebreaking rules:
1. Choose the leftmost on the map (smallest x)
2. Choose the southmost on the map (smallest y)

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
```

Output

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