Задачі
Intersection of Two Prisms
Intersection of Two Prisms
Suppose that \textbf{P_1} is an infinite-height prism whose axis is parallel to the \textbf{z}-axis, and \textbf{P_2} is also an infinite-height prism whose axis is parallel to the \textbf{y}-axis. \textbf{P_1} is defined by the polygon \textbf{C_1} which is the cross section of \textbf{P_1} and the \textbf{xy}-plane, and \textbf{P_2} is also defined by the polygon \textbf{C_2} which is the cross section of \textbf{P_2} and the \textbf{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
\includegraphics{https://static.e-olymp.com/content/c5/c59619d2baff3bd6e9eb5366b08e8a5ecc83074f.jpg}
Figure 3: Intersection of two prisms
Figure 3 shows the intersection of two prisms in Figure 2, namely, \textbf{P_1} and \textbf{P_2}.
Write a program which calculates the volume of the intersection of two prisms.
\InputFile
The input is a sequence of datasets. The number of datasets is less than \textbf{200}.
Each dataset is formatted as follows.
\textbf{m nx_11 y_11x_12 y_12}
\textbf{...x_1m y_1mx_21 z_21x_22 z_22}
\textbf{...x_2n z_2n}
\textbf{m} and \textbf{n} are integers (\textbf{3} ≤ \textbf{m} ≤ \textbf{100}, \textbf{3} ≤ \textbf{n} ≤ \textbf{100}) which represent the numbers of the vertices of the polygons, \textbf{C_1} and \textbf{C_2}, respectively.
\textbf{x_1i}, \textbf{y_1i}, \textbf{x_2j} and \textbf{z_2j} are integers between \textbf{−100} and \textbf{100}, inclusive. (\textbf{x_1i}, \textbf{y_1i}) and (\textbf{x_2j}, \textbf{z_2j}) mean the \textbf{i}^\{-th\} and \textbf{j}^\{-th\} vertices’ positions of \textbf{C_1} and \textbf{C_2} respectively.
The sequences of these vertex positions are given in the counterclockwise order either on the xy-plane or the \textbf{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 \textbf{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.
\OutputFile
For each dataset, output the volume of the intersection of the two prisms, \textbf{P_1} and \textbf{P_2}, with a decimal representation in a line.
None of the output values may have an error greater than \textbf{0.001}. The output should not contain any other extra characters.
Вхідні дані #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
Вихідні дані #1
4.708333333333333 1680.0000000000005 491.1500000000007 0.0 7600258.4847715655