Under construction

Still being built. Things may change

Robot Vacuum

Time limit5sMemory limit128 MB

Summary
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 NN walls and the robot's starting position PP, find the length of the shortest path along which the robot bumps into every wall and then returns to its start PP. 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 NN (3≤N≤1003 \le N \le 100) and the coordinates PxP_x, PyP_y of the robot's starting position (−10 000≤Px,Py≤10 000-10\,000 \le P_x, P_y \le 10\,000). Each of the next NN lines contains the coordinates xx, yy of a wall (polygon) vertex (−10 000≤x,y≤10 000-10\,000 \le x, y \le 10\,000).

The vertices are given in counterclockwise order and every interior angle is less than 180∘180^\circ. 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 xx is the test case number starting from 11 and LL is the length of the shortest path, rounded to two decimal places (rounding at the third decimal digit).

Examples2

  1. Example 1

    Input
    4 0 0
    -1 -1
    1 -1
    1 1
    -1 1
    3 10 1
    0 0
    30 0
    0 20
    
    Expected output
    Case 1: 5.66
    Case 2: 36.73
    
  2. Example 2

    Input
    4 0 0
    -5 -5
    5 -5
    5 5
    -5 5
    
    Expected output
    Case 1: 28.28