Garbage Chute

Time limit1sMemory limit128 MB

Summary
Given a simple polygon, find the minimum width of a vertical strip it can pass through after being rotated, and print it rounded up to two decimals.
Level

Medium7 of 10

Topics
Geometry, Brute force, Implementation, Math
Solved
No attempts yet

Problem

Sunyoung wants to throw away her garbage conveniently, so she decides to install a garbage chute in a building. A garbage chute is a hollow tube: garbage dropped in at the top falls straight down the tube to the basement.

The cost of building the chute is proportional to its size (its width), so it should be made as narrow as possible while still letting the intended object pass through.

Let us simplify the problem to two dimensions. The chute is a vertical passage of a fixed width, and the object is given as a polygon. Before inserting the object you may rotate it to any angle, but once it starts falling it moves straight down without rotating.

In other words, you must rotate the object suitably and then pass it through a vertical strip (the chute) of constant width. Find the minimum chute width through which the given polygon can pass.

Input

The input consists of several test cases. The first line of each test case contains the number of vertices nn of the polygon (3≤n≤1003 \le n \le 100).

Each of the next nn lines contains the coordinates xix_i and yiy_i of a vertex, separated by a space (0≤xi,yi≤1040 \le x_i, y_i \le 10^4). The vertices are given in the order in which they form the polygon.

Within one polygon all vertex coordinates are distinct, and the edges of the polygon do not cross one another. Two adjacent edges sharing a single vertex is not considered a crossing.

A line containing a single 00 follows the last test case and marks the end of the input.

Output

For each test case, print one line in the format Case x: w, where xx is the test case number starting from 1 and ww is the smallest chute width through which the object can pass. Round the width up to a multiple of 0.010.01 and print it with exactly two digits after the decimal point.

Examples1

  1. Example 1

    Input
    3
    0 0
    3 0
    0 4
    4
    0 10
    10 0
    20 10
    10 20
    0
    
    Expected output
    Case 1: 2.40
    Case 2: 14.15