情太くんと立子さんは, 平面の世界にある庭付きの家に住んでいる.二人は点とみなせ, 庭は $N$ 頂点の単純多角形 (隣り合わないどの $2$ 辺も交差も接触もしない多角形) の形をしている.
ある日,二人は一本の伸び縮みするローラーを手に入れた. ローラーは線分とみなせ,ローラーが通過した領域に色を塗ることができる. 二人はローラーを使って庭全体に色を塗りたいと思っている.
作業の前に,二人は以下のような準備を上から順に行う.
準備ができたら,以下のルールに従って塗り始める. ただし,ローラーは杭の上空を通過させることができるが,紐はできない.
さらに,塗り終わったときに以下の条件を満たしていなければならない.
さて,二人はできるだけ離れたくないので,塗っている最中にとる二人の距離の最大値を最小化したい. 二人に代わってそのような値を求めてほしい.
入力は以下の形式で与えられる.$N$ は多角形を構成する頂点の数, $(x_i,y_i)$ はある頂点から始めて時計回りまたは反時計回りに見たときの $i$ 番目の点の座標である.
$N$
$x_1 \ y_1$
$\vdots$
$x_N \ y_N$
$3 \leq N \leq 50$
$|x_i|, |y_i| \leq 100$
全て整数である
頂点は時計回りまたは反時計回りに与えられる
庭の形は単純多角形である
周上の連続する $3$ 点は一直線上に存在しない
答えを $1$ 行で出力せよ.$10^{-5}$ 未満の絶対誤差は許容される.
各サンプルでの庭の形と塗り終わるまでのローラーの動きを図示すると以下のようになる.整数は時刻を表す.図示する都合上ローラーの動きは飛び飛びに示したが,実際には連続的に動いている. ローラーが太くなっている部分で距離の最大値を達成している.
4 0 0 0 1 1 1 1 0
1
3 0 0 0 1 1 0
0.7071067811865476
8 0 0 5 0 5 3 0 3 0 2 4 2 4 1 0 1
1.4142135623730951