Three Silhouettes

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem L: Problem L: 3つのシルエット

JAVA(Japan Aerospace Voyage Agency: 日本宇宙飛行研究機構)は、宇宙開発事業の一環として2003年に探査機を打ち上げた。 この探査機打ち上げの目的の一つに、小惑星イシカワに接近し、その表面物質のサンプルを採集することがある。 様々なアクシデントに見舞われながらも、探査機はイシカワに到達し、そしてついに2010年、地球へ帰還し、イシカワのサンプル試料の入ったカプセルを回収することに成功した。

東京大学を卒業し、JAVAに就職したきたまさ君は、この試料の研究を担当している。 一刻も早く試料の分析をしたいところであるが、とても慎重なきたまさ君は、もしカプセルの中に凶暴なエイリアンが入っていたら大変であると考えた。 そこで、カプセルを開ける前にX線を用いて内部の物質の形状を調べ、エイリアンが入っていないことを確認することにした。 カプセルにX線を当てると、物質が存在しているところは白色に、存在していないところは黒色になった写真が得られる。 様々な角度からX線を当てて写真を得ることにより、内部の物質の形状を特定することができる。

しかし、ここでまた問題が生じた。 正面から、右側面から、上面からの3枚の写真を得たところでX線装置が故障してしまったのである。 さらに、3枚の写真の現像にも失敗し、本来黒色になるべき部分が一部白色となってしまった可能性もある。 このままでは物質の形状を正確に特定することは出来ないため、中にエイリアンが入っていないことを確認できず、カプセルを開けることができない。

研究を続けるためには、X線装置を買い換えるしかないのだが、JAVAには事業仕分けによる予算削減の影響で、X線装置をすぐに買い換えるだけのお金がない。 そこできたまさ君は来年度の予算を増やしてもらい、そのお金で新しいX線装置を買うことを考えた。 もちろん、予算は簡単には増えないため、探査機の成果を最大限にアピールする必要がある。 カプセル中に大きな物質が含まれているほど成果を強くアピールすることができるため、物質が取りうる最大体積を計算することにした。

3枚のX線写真と矛盾しないような内部の物質の形状のうちで、体積が最大であるものを求め、その体積を出力せよ。

Input

各X線写真の白色と黒色の境界は一つの多角形からなる。 多角形は凸とは限らず、また自己交差はしない。 多角形の内側が白色、外側が黒色である。

入力の形式は以下のようである。

nx
y1 z1
y2 z2
 ...
ynx znx
ny
z1 x1
z2 x2
 ...
zny xny
nz
x1 y1
x2 y2
 ...
xnz ynz

nx, ny, nz はそれぞれ、正面・右側面・上面からのX線写真に対応する多角形の頂点数である。 各頂点数は3以上20以下である。 続く n 行には多角形の頂点の座標が反時計回りに与えられる。 頂点の座標は0以上300以下の整数である。

また、座標軸はカプセルの中心から正面方向にx軸を、右側面方向にy軸を、上面方向にz軸を取ってある。

Output

3枚のX線写真と矛盾しないような物質の最大体積を一行に出力せよ。 出力する値は10-3以下の誤差を含んでいても構わない。値は小数点以下何桁表示しても構わない。

Notes on Test Cases

上記入力形式で複数のデータセットが与えられます。各データセットに対して上記出力形式で出力を行うプログラムを作成して下さい。

nx, ny, nz がすべて 0 のとき入力の終わりを示します。

Sample Input

4
0 0
100 0
100 100
0 100
4
0 0
100 0
100 100
0 100
4
0 0
100 0
100 100
0 100
3
0 0
100 0
0 100
3
0 0
100 0
0 100
3
0 0
100 0
0 100
5
0 0
200 0
200 200
100 100
0 200
5
0 0
200 0
100 100
200 200
0 200
4
0 0
200 0
200 200
0 200
0
0
0

Output for Sample Input

1000000.0000
250000.0000
5333333.3333

Source: University of Tokyo Programming Contest 2010 , Tokyo, Japan, 2010
Problem Setter:  Ben Hachimori
http://www.utpc.jp/2010/