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