eolymp
bolt
Try our new interface for solving problems
Problems

Intersection of Two Prisms

Intersection of Two Prisms

Time limit 1 second
Memory limit 32 MiB

Suppose that P_1 is an infinite-height prism whose axis is parallel to the z-axis, and P_2 is also an infinite-height prism whose axis is parallel to the y-axis. P_1 is defined by the polygon C_1 which is the cross section of P_1 and the xy-plane, and P_2 is also defined by the polygon C_2 which is the cross section of P_2 and the xz-plane.

Figure 1 shows two cross sections which appear as the first dataset in the sample input, and Figure 2 shows the relationship between the prisms and their cross sections.

Figure 1: Cross sections of Prisms

Figure 2: Prisms and their cross sections

Figure 3: Intersection of two prisms

Figure 3 shows the intersection of two prisms in Figure 2, namely, P_1 and P_2.

Write a program which calculates the volume of the intersection of two prisms.

Input data

The input is a sequence of datasets. The number of datasets is less than 200.

Each dataset is formatted as follows.

m n x_11 y_11 x_12 y_12

... x_1m y_1m x_21 z_21 x_22 z_22

... x_2n z_2n

m and n are integers (3m100, 3n100) which represent the numbers of the vertices of the polygons, C_1 and C_2, respectively.

x_1i, y_1i, x_2j and z_2j are integers between −100 and 100, inclusive. (x_1i, y_1i) and (x_2j, z_2j) mean the i^{-th} and j^{-th} vertices’ positions of C_1 and C_2 respectively.

The sequences of these vertex positions are given in the counterclockwise order either on the xy-plane or the xz-plane as in Figure 1.

You may assume that all the polygons are convex, that is, all the interior angles of the polygons are less than 180 degrees. You may also assume that all the polygons are simple, that is, each polygon’s boundary does not cross nor touch itself.

The end of the input is indicated by a line containing two zeros.

Output data

For each dataset, output the volume of the intersection of the two prisms, P_1 and P_2, with a decimal representation in a line.

None of the output values may have an error greater than 0.001. The output should not contain any other extra characters.

Examples

Input example #1
4 3
7 2
3 3
0 2
3 1
4 2
0 1
8 1
4 4
30 2
30 12
2 12
2 2
15 2
30 8
13 14
2 8
8 5
13 5
21 7
21 9
18 15
11 15
6 10
6 8
8 5
10 12
5 9
15 6
20 10
18 12
3 3
5 5
10 3
10 10
20 8
10 15
10 8
4 4
-98 99
-99 -99
99 -98
99 97
-99 99
-98 -98
99 -99
96 99
0 0
Output example #1
4.708333333333333
1680.0000000000005
491.1500000000007
0.0
7600258.4847715655
Source ACM ICPC Regionals 2010, Asia, Tokyo