eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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 секунда
Ліміт використання пам'яті 32 MiB
Вхідні дані #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
Джерело ACM ICPC Regionals 2010, Asia, Tokyo