## 10876 - Factory Robot

Moderator: Board moderators

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

### 10876 - Factory Robot

Need some hint.
All ideas that come to me are very unimplementabe
(it's rely on Voronoi Diagram )

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

.
.
.
.
.
.
.

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.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Very good and simple idea!
I easily got AC, thanks.

ffd
New poster
Posts: 1
Joined: Sun Apr 09, 2006 10:18 am
Any testing I/O?

Don't know why I still get WA...