Garbage Chute
Time limit1sMemory limit128 MB
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 of the polygon ().
Each of the next lines contains the coordinates and of a vertex, separated by a space (). 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 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 is the test case number starting from 1 and is the smallest chute width through which the object can pass. Round the width up to a multiple of and print it with exactly two digits after the decimal point.