Задача D. Пересечение двух тетраэдров (ОНТИ)

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Имеются два трехмерных симплекса (тетраэдра), каждый из которых задан координатами четырех своих вершин:

(x1, y1, z1), (x2, y2, z2), (x3, y3, z3), (x4, y4, z4).

Требуется определить объем тела, полученного путем пересечения указанных тетраэдров.

Формат входных данных

Во входных данных последовательно записаны координаты сначала первого, а затем второго тетраэдра.

Формат выходных данных

Выходные данные должны содержать ответ, указанный с точностью до 5-го знака после запятой.

Ограничения

Вершины отдельно взятого тетраэдра не лежат в одной плоскости.

10 < (xi, yi, zi) < 10.

Примеры тестов

Стандартный вход Стандартный выход
1
-1.00000 -1.00000  0.00000
 2.00000  0.00000  0.00000
 0.00000  0.00000  2.00000
 0.00000  2.00000  0.00000

 2.00000  0.00000  0.00000
 1.00000  1.00000  2.50000
 0.00000  0.00000  0.00000
 1.00000  2.00000  0.00000
0.49383
2
-1.00000  1.00000  3.80960
 0.00000  1.50000  1.50000
 3.00000 -1.00000  0.00000
 0.00000  2.50000  4.00000

-2.00000  3.00000 -0.50000
 3.00000  4.00000  0.00000
 2.50000  3.00000  1.00000
 3.00000  4.00000  3.60700
0.00000

0.039s 0.008s 15