はんぶんこ

双子の姉弟ヤエちゃんとジョー君は、お母さんからおやつに煎餅を１枚もらいました。その煎餅は凸多角形の形をしていて、割りやすいようにすべての対角線上に切れ込みが入っています。

２人は煎餅をはんぶんこにしたいのですが、力がないので、１本の対角線の両側を手ではさんで割るしかありません。姉弟は、どの対角線に沿って煎餅を２つに割ったら、はんぶんこに一番近くなって、２人の取り分の差が最も小さくなるか考え始めました。

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

入力

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

$N$
$x_1$ $y_1$
$x_2$ $y_2$
:
$x_N$ $y_N$

１行目に凸多角形の頂点の数$N$ ($4 \leq N \leq 60,000$)が与えられる。続く$N$行に凸多角形の頂点の座標$x_i, y_i$ ($0 \leq x_i, y_i \leq 100,000,000$)が整数で与えられる。凸多角形の頂点は、隣り合った頂点を反時計回りに訪問するような順番で与えられる。

出力

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

入出力例

入力例１

4
0 0
1 0
1 1
0 1

出力例１

0.0

入力例２

4
0 0
1 0
1 2
0 1

出力例２

0.5000

 

Note

Algorithm

 

---