1143 : 三角形和矩形

Description

Bobo 有一个三角形和一个矩形，他想求他们交的面积。

具体地，三角形和矩形由 8 个整数 x1,y1,x2,y2,x3,y3,x4,y4 描述，表示三角形的顶点坐标是 (x1,y1),(x1,y2),(x2,y1)， 矩形的顶点坐标是 (x3,y3),(x3,y4),(x4,y4),(x4,y3).

Input

输入包含不超过 30000 组数据。

每组数据的第一行包含 4 个整数 x1,y1,x2,y2 (x1 ≠ x2, y1 ≠ y2).

第二行包含 4 个整数 x3,y3,x4,y4 (x3<x4,y3<y4).

(0 ≤ xi, yi ≤ 10⁴)

Output

对于每组数据，输出一个实数表示交的面积。绝对误差或相对误差小于 10^− 6 即认为正确。

Sample

1 1 3 3
0 0 2 2
0 3 3 1
0 0 2 2
4462 1420 2060 2969
4159 257 8787 2970

1.00000000
0.75000000
439744.13967527

Hint

Source

Author

ftiasch