# UVa 10687

Jump to navigation
Jump to search

## Contents

## 10687 - Monitoring the Amazon[edit]

## Summary[edit]

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[edit]

Construct the graph, and use any of the Graph Connectivity algorithms. Since *V* is at most 1000, implementation will do.

## Gotcha's[edit]

- Remember the tiebreaking rules:
- Choose the leftmost on the map (smallest x)
- Choose the southmost on the map (smallest y)

## Implementations[edit]

## Input[edit]

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[edit]

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