Дистанционная подготовка: Две веревки
Две веревки
от Евгений Соколов - Среда 12 Декабрь 2007, 18:27
  Задача с пятой личной интернет-олимпиады:

Мальчик Вася серьезно увлекается топологией. В свободное от учебы время он часто экспериментирует с веревками: переплетает их между собой, завязывает на них узлы, а потом исследует топологические свойства получающихся переплетений. Вчера Вася сплел хитроумную конструкцию из двух веревок красной и черной, а затем соединил концы красной веревки между собой, замкнув ее. Точно так же он поступил и с черной веревкой. Теперь Вася поставил перед собой задачу выяснить, можно ли разъединить эти веревки, не разрывая и не развязывая их. Разумеется, для этого он запретил себе прикасаться к веревкам, и стал решать эту задачу в уме.

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

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

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

В первой строке входного файла находится число N (1 <= N <= 5) - количество тестов в файле.
Далее идет N описаний тестов.
Первая строка теста содержит числа M и K (3 <= M,K <= 50) количество вершин в ломаных, задающих красную и черную веревку соответственно. Далее идут M строк, задающих красную веревку. В каждой из этих строк содержится 3 целых числа X_i , Y_i , Z_i - координаты вершины ломаной. Следующие K строк в аналогичном формате задают черную веревку.
Для каждого теста гарантируется следующее:
. заданные ломаные плоские (различные ломаные, возможно, лежат в разных плоскостях);
. звенья ломаных не имеют общих точек (за исключением точек, соединяющих последовательные звенья одной ломаной);
. все заданные точки уникальны;
. координаты точек не превосходят 10^3 по абсолютному значению.

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

Для каждого теста из входного файла выведите строку YES, если веревки возможно разделить, и NO, если нельзя.


В целом идея решения понятна: для каждого звена черной веревки ищем точку пересечения с плоскостью красной веревки, затем проверяем, лежит ли эта точка внутри многоугольника, образуемого красной веревкой. Но как все это реализовать?