Boomerang

Problem Description
Australia original inhabitants used to hunt by a weapon called "boomerang". When a boomerang is thrown out, it rotates, hits the target, and then return to the thrower. ZXX is the best boomerang thrower in Australia. His skill is so wonderful that his boomerang can do any rotation he wants in the air. He travels around to show his skill and make money. One of his classic show is to throw out the boomerang, and it will pass through between two very close pillars. Of course the boomerang must fly parallel to the ground. If not so, everybody can do it. ZXX always puts the two pillars as close as possible to show his skill, but he wants you to figure out the smallest distance between two pillars which allows his boomerang to go through.

To simplify the problem, you can consider the boomerang as a simple polygon in a 2D plane, and each of its edge is parallel to x-axis or y-axis. Each interior angle is either 90 degrees or 270 degrees. Two pillars can be considered as two points.

This illustration simply shows how a boomerang passes through two pillars:

Input
The input consists of several test cases (less than 500).Each test case begins with an integer n (4<=n<=8), representing the number of vertices of a polygon. Next n lines give coordinates of n vertices in order. Each line contains two integers xi, yi(|xi|, |yi|<=100000). For each test case there are no two vertices is in the same place.

Input ends with n=0.

Output
For each test case, print a single real number w, representing the minimum distance to ensure the boomerang can pass through. The answer should be rounded to 2 digits after the decimal point.

Sample Input
6
0 0
100 0
100 1
1 1
1 100
0 100
8
0 0
30 0
30 30
20 30
20 10
10 10
10 30
0 30
0

Sample Output
1.41
14.14

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问