You are working for a company designing cute, funny robot
vacuum cleaners. At a high level, the robots’ behavior is
divided into three modes:
Unfortunately, while consumer testing shows that the last
two modes are working perfectly, the exploration mode still has
bugs. You’ve been put in charge of debugging.
At the beginning of the exploration mode, the robot is
placed into a convex polygonal room. It has sensors that should
tell it where all the walls are. Your job is to write a program
that verifies that these readings are correct. To do this, the
robot needs to physically touch every wall in the room.
Your problem is this: given the shape of a convex polygonal
room with $N$ walls and a
starting point $P$ inside
it, determine the shortest route that touches each wall and
then returns to $P$.
Touching a corner counts as touching both incident walls.
Each test case starts with a line containing the number of
vertices $N$ of the
polygon ($3 \leq N \leq
100$) and the integer coordinates $P_ x$ and $P_ y$ of the robot’s starting point
$(-10\, 000~ \leq ~ P_ x,P_ y~
\leq ~ 10\, 000)$. This is followed by $N$ lines, each containing two
integers $x$, $y$ ($-10\, 000 \leq x,y \leq 10\, 000$)
defining a vertex of the polygon. Vertices are given in
counterclockwise order, all interior angles are less than 180
degrees, the polygon does not self-intersect, and the robot’s
starting point is strictly inside the polygon.
For each test case, display the case number and the length
of the desired route, with exactly two decimal places.
|Sample Input 1
||Sample Output 1
4 0 0
3 10 1
Case 1: 5.66
Case 2: 36.73