Пересечение двух призм
Представьте себе две бесконечно высокие призмы: P_1, ось которой параллельна оси z, и P_2, ось которой параллельна оси y. Призма P_1 определяется многоугольником C_1, который является её поперечным сечением в плоскости xy, а призма P_2 определяется многоугольником C_2, который является её поперечным сечением в плоскости xz.
На Рисунке 1 показаны два поперечных сечения, соответствующие первому набору данных в примере ввода, а на Рисунке 2 изображена взаимосвязь между призмами и их поперечными сечениями.
Рисунок 1: Поперечные сечения призм
Рисунок 2: Призмы и их поперечные сечения
Рисунок 3: Пересечение двух призм
На Рисунке 3 показано пересечение призм P_1 и P_2, изображённых на Рисунке 2.
Ваша задача — написать программу, которая вычисляет объем пересечения этих двух призм.
Входные данные
Ввод состоит из последовательности наборов данных. Количество наборов данных не превышает 200.
Каждый набор данных имеет следующий формат:
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 и n — целые числа (3 ≤ m ≤ 100, 3 ≤ n ≤ 100), обозначающие количество вершин многоугольников C_1 и C_2 соответственно.
x_1i, y_1i, x_2j и z_2j — целые числа в диапазоне от −100 до 100 включительно. Координаты (x_1i, y_1i) и (x_2j, z_2j) представляют позиции i-й и j-й вершин многоугольников C_1 и C_2 соответственно.
Позиции вершин даны в порядке против часовой стрелки на плоскости xy или xz, как показано на Рисунке 1.
Вы можете считать, что все многоугольники выпуклые, то есть все их внутренние углы меньше 180 градусов. Также можно предположить, что все многоугольники простые, то есть их границы не пересекаются и не касаются сами себя.
Конец ввода обозначается строкой, содержащей два нуля.
Выходные данные
Для каждого набора данных выведите объем пересечения призм P_1 и P_2 в виде десятичного числа на отдельной строке.
Каждое значение должно быть вычислено с точностью до 0.001. Вывод не должен содержать никаких лишних символов.