006 - はんぶんこ

問題文

双子の姉弟ヤエちゃんとジョー君は、お母さんからおやつに煎餅を$1$枚もらいました。その煎餅は凸多角形の形をしていて、割りやすいようにすべての対角線上に切れ込みが入っています。 $2$人は煎餅をはんぶんこにしたいのですが、力がないので、$1$本の対角線の両側を手ではさんで割るしかありません。姉弟は、どの対角線に沿って煎餅を$2$つに割ったら、はんぶんこに一番近くなって、 $2$人の取り分の差が最も小さくなるか考え始めました。

課題

凸多角形によって表される煎餅の形についての情報が与えられたとき、$2$人の取り分の差の最小値を求めるプログラムを作成せよ。
ただし、$2$人の取り分の差は、$1$本の対角線に沿って煎餅を$2$つに分割したときの、それらの面積の差の絶対値で表される。

入力

入力は以下の形式で与えられる。

$N$
$x_{1} \ y_{1}$
$x_{2} \ y_{2}$
$\vdots$
$x_{N} \ y_{N}$

$1$行目に凸多角形の頂点の数$N \ (4 \leq N \leq 60,000)$が与えられる。続く$N$行に凸多角形の頂点の座標$x_{i},y_{i} \ (0 \leq x_{i},y_{i} \leq 100,000,000)$が整数で与えられる。 凸多角形の頂点は、隣り合った頂点を反時計回りに訪問するような順番で与えられる。
入力に対して、実行時間が$3$秒を超えてはならない。

出力

$2$人の取り分の差の最小値を実数で$1$行に出力する。ただし、誤差がプラスマイナス $0.0001$ を超えてはならない。
この条件を満たせば小数点以下は何桁表示してもよい。

入出力例

入力例1

4
0 0
1 0
1 1
0 1

出力例1

0.0

入力例2

4
0 0
1 0
1 2
0 1

出力例2

0.5000