Robot Vacuum
Time limit5sMemory limit128 MB
Given a convex polygon and an interior start point, find the shortest closed route that touches (or bumps into) every edge and returns to the start.
- Level
Hard8 of 10
- Topics
- Geometry, Greedy, Dynamic programming, Shortest path
- Solved
- No attempts yet
Problem
A robot vacuum must recognize the layout of a room before it starts cleaning. Its sensor can only recognize a wall that the robot has physically bumped into, so to recognize every wall the robot must bump into all of the room's walls.
The room is shaped like a convex polygon. Given a room with walls and the robot's starting position , find the length of the shortest path along which the robot bumps into every wall and then returns to its start . If the robot bumps into a vertex of the polygon, it counts as bumping into both walls that meet at that vertex.
Input
The input consists of several test cases.
The first line of each test case contains the number of polygon vertices () and the coordinates , of the robot's starting position (). Each of the next lines contains the coordinates , of a wall (polygon) vertex ().
The vertices are given in counterclockwise order and every interior angle is less than . The polygon's edges do not intersect one another, and the robot's starting position is strictly inside the polygon (never on an edge).
Output
For each test case, print one line in the form Case x: L, where is the test case number starting from and is the length of the shortest path, rounded to two decimal places (rounding at the third decimal digit).