G : Bob's Bomb / 爆弾

問題文

街に N 棟の建物が立っている。街は (50,50),(−50,50),(−50,−50),(50,−50) を頂点とする正方形であり、建物 i は a_i 角柱の形をしている。

ボブはこれら全ての建物を爆弾を 1 つだけ使って破壊したい。爆発させられる地点は、街の中の地上で建物の外または境界上の点である。

爆弾は爆発すると周囲 360 度に向かって爆風を出す。建物は爆弾に「しっかり面している」と爆風によって破壊される。建物 i に「しっかり面している」とは、建物 i 以外の全ての建物を無視したときに建物 i の爆弾に面している側面が、建物 i 以外を無視しない場合にも他の建物の影にならないことを意味する。ある辺を延長した直線上に爆弾がある場合は面しているとみなさない。具体的にはサンプルを参照してほしい。

以上の目的を達成する爆発地点としてありうる場所からなる領域の面積を求めよ。

入力

入力は以下の形式からなる。 (x_{ij} , y_{ij}) は建物 i の底面の j 番目の頂点の座標である。

N
a_1 x_{11} y_{11} x_{12} y_{12} … x_{1{a_0}} y_{1{a_0}}
a_2 x_{21} y_{21} x_{22} y_{22} … x_{2{a_1}} y_{2{a_1}}
…
a_N x_{N1} y_{N1} x_{N2} y_{N2} … x_{N{a_N}} y_{N{a_N}}

制約

• 入力はすべて整数である
• 入力は全て凸多角形である
• 異なる多角形の共通部分の面積は 0 である
• 1 \≤ N \≤ 6
• 3 \≤ a_i \≤ 6
• {\rm max} ({\rm abs}(x_{ij}),{\rm abs}(y_{ij})) \≤ 50

出力

条件を満たす点が存在するならその点からなる領域の面積を出力せよ。10^{−6} 未満の誤差は許される。存在しない場合は −1 と出力せよ。

サンプル

サンプル入力1

4
4 5 5 5 30 30 30 30 5
4 5 -5 5 -30 30 -30 30 -5
4 -5 5 -5 30 -30 30 -30 5
4 -5 -5 -5 -30 -30 -30 -30 -5

サンプル出力1

140.000000

中央の八角形で条件を満たす。この領域から出るといずれかの面が他の正方形の影になる。

サンプル入力2

3
3 -10 0 -20 0 -15 15
3 -10 0 -20 0 -15 -15
4 10 10 20 10 20 -10 10 -10

サンプル出力2

0.000000

中央の長さ 20 の線分で条件を満たす。面を作らなくても条件を満たす点は存在しうる。爆弾が辺を延長した直線上にある場合は面しているとみなさない。

サンプル入力3

3
4 0 10 10 10 10 -10 0 -10
4 11 10 21 10 21 -10 11 -10
4 22 10 32 10 32 -10 22 -10

サンプル出力3

-1

街の中に条件を満たす点は存在しない。

サンプル入力4

3
4 -4 0 -4 -50 -2 -50 -2 0
4 -1 0 -1 -50 1 -50 1 0
4 4 0 4 -50 2 -50 2 0

サンプル出力4

0.000000

街の境界上に 1 点のみ存在する。

---