Поход в горы
Елена путешествует со своими друзьями в высокогорье. Их план состоит в том, чтобы отправиться из своего лагеря A в прекрасное место B.
К сожалению, у Елены началось головокружение из-за высотной болезни. Помогите ее группе найти такой маршрут, чтобы максимальная высота на нем была как можно меньше.
Входные данные
Содержит полную информацию о ландшафте квадратного региона 10^6 * 10^6 в следующем формате. Первая строка содержит количество треугольников в ландшафте n (2 ≤ n ≤ 2000). Каждая из следующих n строк содержит девять целых чисел x[i1], y[i1], z[i1], x[i2], y[i2], z[i2], x[i3], y[i3], z[i3] - координаты треугольника. Все координаты принадлежат интервалу [0, 10^6]. Каждая из двух последних строк содержит три целых числа x[A], y[A], z[A] и x[B], y[B], z[B] - координаты лагеря A и прекрасного места B.
Заданные треугольники гарантированно описывают согласованный непрерывный ландшафт. Проекции треугольников на плоскость XY невырождены и заполняют квадрат без перекрытия. Вершина одного треугольника никогда не лежит внутри края другого треугольника. Точки A и B принадлежат поверхности ландшафта и различны.
Выходные данные
Вывести маршрут в виде ломаной от A до B с наименьшей наивысшей точкой. В первой строке вывести количество вершин в ломаной m. В каждой из следующих m строк вывести три целых чиса - координаты вершины ломаной: x[i], y[i] и z[i]. Вершины следует вывести в порядке их расположения на ломаной, от A до B (включая эти две точки).
Все координаты вершин ломаной должны быть целыми. Каждый отрезок ломаной должен принадлежать некоторому входному треугольнику (возможно стороне треугольника). Количество вершин в ломаной не должно превышать 5n.