2017-11-21 15:41


  • Golang
  • parallel
  • it
  • less
  • lines

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:

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.

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
0 0
100 0
100 1
1 1
1 100
0 100
0 0
30 0
30 30
20 30
20 10
10 10
10 30
0 30

Sample Output

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享