Задача F. Пересечение двух пластин

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

Условие

Пусть имеются две круглые плоские пластины, расположенные в трехмерном пространстве. Каждая такая пластина однозначно задается координатами трех не совпадающих между собой точек, лежащих на ее границе.

В рамках текущей задачи требуется определить наличие пересечения между указанными пластинами. Будем считать, что пластины пересекаются, если у них имеется как минимум одна общая точка.

Формат входного файла

В начале входного файла "input.txt" хранятся вещественные координаты точек, задающих 1-ю из имеющихся пластин: (x1, y1, z1), (x2, y2, z2) и (x3, y3, z3). Далее следуют координаты точек, задающих 2-ю пластину: (x4, y4, z4), (x5, y5, z5) и (x6, y6, z6).

Формат выходного файла

Выходной файл "output.txt" должен содержать одно из следующих значений:

1 — если заданные пластины пересекаются;

0 — в противном случае.

Ограничения

Полагается, что каждая из указанных пластин является невырожденной. Иначе говоря, задающие ее точки не лежат на одной прямой.

Все тесты подобраны таким образом, чтобы исключить влияние погрешности машинного округления на результат решения.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
 1.37001 -8.96720 -5.08104
-9.09250 -0.15130 -8.70300
 9.07213 -5.40160  4.09015
 7.58011  8.42032  9.03280
-1.34060  2.07613 -5.17640
 5.04500  7.18045  1.03409
1
2
 0.37001 -8.76004 -5.38004
-4.09250  0.20150  7.10350
 5.07011 -5.40160  3.59182
 8.94060  7.42032 -0.33687
 1.50300  8.07600  5.74690
-9.04500  3.02401  1.00830
0

0.128s 0.020s 17