Поход в горы
Поход в горы
Елена путешествует со своими друзьями в высокогорье. Их план состоит в том, чтобы отправиться из своего лагеря A в прекрасное место B.
К сожалению, у Елены началось головокружение из-за высотной болезни. Помогите ее группе найти такой маршрут, чтобы максимальная высота на нем была как можно меньше.
Входные данные
Содержит полную информацию о ландшафте квадратного региона 106
* 106
в следующем формате. Первая строка содержит количество треугольников в ландшафте n (2 ≤ n ≤ 2000). Каждая из следующих n строк содержит девять целых чисел xi1
, yi1
, zi1
, xi2
, yi2
, zi2
, xi3
, yi3
, zi3
- координаты треугольника. Все координаты принадлежат интервалу [0, 106
]. Каждая из двух последних строк содержит три целых числа xA
, yA
, zA
и xB
, yB
, zB
- координаты лагеря A и прекрасного места B.
Заданные треугольники гарантированно описывают согласованный непрерывный ландшафт. Проекции треугольников на плоскость XY невырождены и заполняют квадрат без перекрытия. Вершина одного треугольника никогда не лежит внутри края другого треугольника. Точки A и B принадлежат поверхности ландшафта и различны.
Выходные данные
Вывести маршрут в виде ломаной от A до B с наименьшей наивысшей точкой. В первой строке вывести количество вершин в ломаной m. В каждой из следующих m строк вывести три целых чиса - координаты вершины ломаной: xi
, yi
и zi
. Вершины следует вывести в порядке их расположения на ломаной, от A до B (включая эти две точки).
Все координаты вершин ломаной должны быть целыми. Каждый отрезок ломаной должен принадлежать некоторому входному треугольнику (возможно стороне треугольника). Количество вершин в ломаной не должно превышать 5n.
8 1000000 0 0 1000000 1000000 150000 600000 600000 400000 0 1000000 0 600000 600000 400000 600000 1000000 300000 0 1000000 0 400000 300000 150000 600000 600000 400000 400000 0 200000 1000000 0 0 400000 300000 150000 400000 300000 150000 1000000 0 0 600000 600000 400000 600000 600000 400000 1000000 1000000 150000 600000 1000000 300000 0 0 0 400000 0 200000 400000 300000 150000 0 1000000 0 0 0 0 400000 300000 150000 100000 700000 37500 900000 400000 137500
5 100000 700000 37500 0 1000000 0 400000 300000 150000 1000000 0 0 900000 400000 137500