10876 - Factory Robot

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10876 - Factory Robot

Post by kp » Wed Jun 29, 2005 2:08 am

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

Post by misof » Wed Jun 29, 2005 10:00 am

Spoiler alert. Don't read on if you want to solve the problem on your own.

.
.
.
.
.
.
.

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

Post by kp » Wed Jun 29, 2005 12:44 pm

Very good and simple idea!
I easily got AC, thanks.

ffd
New poster
Posts: 1
Joined: Sun Apr 09, 2006 10:18 am

Post by ffd » Sun Apr 09, 2006 10:26 am

Any testing I/O?

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

Post Reply

Return to “Volume 108 (10800-10899)”