問題文

$3$ 次元 $xyz$ 座標空間内に、軸が $z$ 軸と平行であり、長さ無限大の柱状の物体 $V$ があります。

物体 $V$ を $xy$ 平面に平行な平面で切断すると、その断面は切断する位置にかかわらず同じ形状になります。この図形を平面 $z=0$ で切断したとき、その切断面は各 $i(1 \leq i \leq N)$ に対し、頂点 $A_i$ と $A_{i+1}$ を結んだ $N$ 角形となります。なお、各 $i,j(1 \leq i,j \leq N)$ に対し、頂点 $A_i,A_{i+1},A_{i+2}$ が全て同一直線状に存在することはなく、この $N$ 角形は自己交差を含まないとは限らず、$i \neq j$ のとき $A_i$ と $A_j$ の座標は異なっています。ここで、頂点 $A_{N+1}$ は頂点 $A_1$ のことを、頂点 $A_{N+2}$ は頂点 $A_2$ のことを表します。

また、各 $i(1 \leq i \leq N)$ に対し、頂点 $A_i$ の座標は $(x_i,y_i,0)$ です。

この物体 $V$ を、常に最低でも $1$ 辺を平面 $y=0$ と共有しながら、平面 $y=0$ と平面 $y=\sqrt{H}$ で挟まれる空間内を転がすことを考えます。

このとき、物体 $V$ を好きなだけ転がすことができるための $H$ の最小値を求めてください。

制約

• $3 \leq N \leq 2000$
• $-10000 \leq x_i,y_i \leq 10000$
• 入力は全て整数

入力

出力

$H$ の最小値を出力してください。

サンプル

4
0 0
0 1
1 1
1 0

2

断面は $1$ 辺の長さが $1$ の正方形となっています。

4
0 0
0 1
1 0
1 1

2

与えられる図形が自己交差を含むこともあります。