Breaking Biscuits

Time limit1sMemory limit512 MB

Summary

Given a simple polygon, find the smallest diameter of a circular mug that can contain it in some orientation, i.e. the polygon's minimum width.

Level: Medium7 of 10
Topics: Geometry, Two pointers, Sorting
Solved: No attempts yet

Problem

Walter's office switched the weekly break room biscuit order to a different brand. The new biscuits have two properties that matter here.

A biscuit is completely flat, so it is a plane figure.
The outline of a biscuit is a simple polygon.

The mugs already in the break room all turned out to be too narrow. Walter cannot dunk one of the new biscuits into any of them, however he turns the biscuit about the three axes, so he is ordering another mug.

Work out how wide that mug has to be. Given the outline of one biscuit, find the smallest mug diameter that still lets the biscuit go fully inside in at least one orientation.

Input

The first line contains one integer $N$ ( $3 \le N \le 100$ ), the number of vertices of the biscuit.
Each of the next $N$ lines contains two space separated integers $X_i$ and $Y_i$ ( $-10^5 \le X_i, Y_i \le 10^5$ ), the coordinates of the $i$ -th vertex.

The vertices are always given in anti-clockwise order. The outline never crosses itself, and the biscuit has positive area.

Output

Print the smallest mug diameter that admits the biscuit in at least one orientation, with exactly 6 digits after the decimal point. In every test case the answer is more than $10^{-9}$ away from a rounding tie, so rounding at the seventh decimal place is unambiguous.

Examples3

Example 1
Input
```
4
0 0
5 0
5 2
0 2
```
Expected output
```
2.000000
```

Example 2

Input

6
81444 14017
80944 13517
81127 12834
81810 12651
82310 13151
82127 13834

Expected output

1224.708945

Example 3

Input

Expected output

28.816782