/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
地面に直方体のブロックを埋めたところ、凸六角形の穴が開きました。穴の形が与えられたときブロックの体積として考えられる最小値を求めてください。
ブロックを xyz 空間内の直方体とします。また、地面を平面 z = 0 とします。このとき、穴は直方体と平面 z = 0 の共通部分として表されます。穴が凸六角形であり、その頂点の座標が反時計回りに (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5), (x_6, y_6) であるとき、直方体の体積として考えられる最小値を求めてください。ただし、そのような直方体が存在しない場合は、-1 と出力してください。
入力
入力は以下の形式で標準入力から与えられる。
x_1 y_1 x_2 y_2 x_3 y_3 x_4 y_4 x_5 y_5 x_6 y_6
- 入力はすべて整数である。
- 0 ≤ x_i, y_i ≤ 1000 をみたす。
- 六点 (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5), (x_6, y_6) は反時計回りに並んでいる。とくに、入力中の三点が同一直線上に並んでいることはない。
- 入力される六角形は凸である。
出力
ブロックの体積として考えられる最小値を出力せよ。ただし、条件を満たす直方体が存在しない場合は -1 と出力せよ。 絶対誤差または相対誤差が 10^{-6} 以下ならば正解となる。 出力の末尾には改行を入れること。
入力例1
1 4 0 2 1 0 4 0 5 2 4 4
出力例1
43.301270189
入力例2
0 0 1 1 2 4 3 9 4 16 5 25
出力例2
-1
Problem
We made a convex-hexagonal hole on the ground by burying a hyperrectangular block into the ground. You will be given the shape of the hole. Compute the minimum possible volume of the block.
Formally, the problem statement is as follows. Let the block be a hyperrectangle in a three-dimensional xyz-space. Let z = 0 be the surface of the ground. Then, the hole can be represented as the intersection between the hyperrectangle and the plane z = 0. When the hole is a convex hexagon and its vertices are (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5), (x_6, y_6) (in counter-clockwise order), compute the minimum possible volume of the hyperrectangle. If there is no such hyperrectangle, print -1 instead.
Input
The input will be given in the following format from the standard input:
x_1 y_1 x_2 y_2 x_3 y_3 x_4 y_4 x_5 y_5 x_6 y_6
- All numbers in the input will be integers.
- The coordinates will satisfy 0 ≤ x_i, y_i ≤ 1000.
- The six points (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5), (x_6, y_6) will be arranged in the counter-clockwise order. In particular, no three points will be on the same line.
- The hexagon will be convex.
Output
Print the minimum possible volume of the hyperrectangle. In case there is no such hyperrectangle, print -1 instead. The output will be considered correct if its absolute error or relative error is at most 10^{-6}. Print a newline at the end of the output.
Input Example 1
1 4 0 2 1 0 4 0 5 2 4 4
Output Example 1
43.301270189
Input Example 2
0 0 1 1 2 4 3 9 4 16 5 25
Output Example 2
-1