E: Do You Divide It? / 切り刻む気か？

物語

T君は過去に出場したプログラミングコンテストで平面図形の問題にひどく手こずらされ，それ以来，平面図形に強い恨みを抱いている．

中でも，特に二次元平面上に描かれる多角形に対して複雑な感情を抱いているため，多角形を見かけると切り刻まずにはいられない．

T君が多角形を切り刻むときには，y軸に平行に幅0.5の間隔でスリットの入った板で多角形を覆い，スリットで見えない部分を切り刻んで捨ててしまう．

しかしながら，T君は一方的な殺戮を好まないため，多角形に再起の芽を残すべく，切り刻んだ後に残る図形の合計面積ができるだけ大きくなるように配慮する．

T君が切り刻んだ後に残る図形の面積を求めよう．

問題

二次元平面にy軸方向無限長のスリットが入っており，x軸方向に0.5ごとに見える部分と見えない部分が切り替わるようになっている．

下図のように，この平面上で，N個の頂点からなる多角形がx軸正方向に向けて平行移動し続ける．

多角形が見える部分が最も大きくなる瞬間の，見えている部分の面積を出力せよ．

入力形式

1行目でNを与える．続くN行のi行目で，多角形の反時計回りでのi番目の頂点座標(x_i,y_i)を与える．

以下を仮定してよい．

• 入力はすべて整数
• 3 ≤ N ≤ 100, −10^3 ≤ x_i, y_i ≤ 10^3
• 与えられる多角形は，隣接する線分以外と辺や頂点を共有することはない
• 与えられる多角形の連続する3つの頂点は同一直線上にない

出力形式

与えられた多角形の見える部分が最も大きくなる瞬間の，見える面積を1行で出力せよ． 絶対誤差，相対誤差は 10^{−5} まで許容する．

入力例1

6
0 0
-1 -2
3 -2
2 0
3 2
-1 2

出力例1

6.000000000

入力例2

5
0 0
2 -2
4 -2
4 2
2 2

出力例2

6.50000000

Note

Link

 

---