Need some hint.

All ideas that come to me are very unimplementabe

(it's rely on Voronoi Diagram )

## 10876 - Factory Robot

**Moderator:** Board moderators

.

.

.

.

.

.

.

Imagine a graph with N+4 vertices -- one for each pillar and one for each wall of the factory. Suppose that you know the radius R of the robot. Connect those pairs of vertices that are too close for the robot to pass between them. Now there are two possible cases:

- If two "wall" vertices are in the same component, clearly there is a pair of corners such that the robot cannot walk from one of them to the other.

- Otherwise: there is enough space in each of the corners (a pillar too close to the corner would be connected with both its walls) and the robot can walk between each two of them.

Thus all you have to do is to find the minimum R for which the resulting graph is connected. This can be done in many ways, in the contest I did it using the Union/FindSet algorithm.