Jeju Island

Time limit1sMemory limit128 MB

Summary

Given a convex polygon, find the point maximizing distance to the boundary using ternary search or half-plane shrinking, and output that maximum distance.

Level: Medium7 of 10
Topics: Geometry, Binary search, Divide and conquer
Solved: No attempts yet

Problem

During the Chuseok holidays, Sanggeun decided to take a trip to Jeju Island, famous for its beautiful natural scenery. While looking at a map of Jeju Island and planning his trip, he suddenly wondered which spot lies farthest from the sea.

Given the map of the island, write a program that computes how far from the sea the point farthest from the sea lies. The distance of a point from the sea is the distance from that point to the boundary of the island (its nearest edge). The island is a convex, simple polygon.

Input

The input consists of several test cases. The first line of each test case contains the number of vertices $n$ ( $3 \le n \le 100$ ). Each of the next $n$ lines contains the $x$ and $y$ coordinates of a vertex, given in counterclockwise order. The polygon consists of the segments $(x_i, y_i)-(x_{i+1}, y_{i+1})$ ( $1 \le i \le n-1$ ) and $(x_n, y_n)-(x_1, y_1)$ . All coordinates are between $0$ and $10000$ inclusive.

The last line of the input contains a single $0$ , which marks the end of the input.

Output

For each test case, output on its own line the distance from the sea to the point on the island that is farthest from the sea. Round the value to five decimal places and print exactly five digits after the decimal point (for example, 12.30000).

Examples1

Example 1

Input

4
0 0
10000 0
10000 10000
0 10000
3
0 0
10000 0
7000 1000
6
0 40
100 20
250 40
250 70
100 90
0 70
3
0 0
10000 10000
5000 5001
0

Expected output