Description

$P$ has $N$ vertices $P_1, P_2, P_3, \dots, P_N$. The coordinates of vertex $P_i$ in the 2D plane are $(x_i, y_i)$. The vertices are given in clockwise order.

Li Bin may choose a real number $D$, then move each vertex by at most $D$ units. Now he wants to know the minimal value of $D$ that makes this convex polygon no longer convex.

Input Format

The first line contains $1$ integer $N$.

The next $N$ lines each describe a vertex with two integers, the $x_i$ and $y_i$ of that vertex. The vertices are given in clockwise order and form a strictly convex polygon.

Output Format

Output a real number $D$, representing the minimal $D$ that makes this polygon non-convex.

Let your answer be $a$ and the standard answer be $b$. You are correct if and only if $\frac{|a - b|}{\max(1, b)} \le 10^{-4}$.

4
0 0
0 1
1 1
1 0

0.3535533906

6
5 0
10 0
12 -4
10 -8
5 -8
3 -4

1.0000000000

Hint

Constraints: For $100\%$ of the testdata, $4 \le N \le 1000$, $-10^9 \le x_i, y_i \le 10^9$.

Translated by ChatGPT 5