Слалом
Несмотря на редкость снегопадов в Мадриде, интерес к зимним видам спорта в городе растет, особенно к лыжному спорту. Многие жители проводят несколько выходных или даже целые недели, совершенствуя свои навыки в горах.
В этой задаче мы сосредоточимся на одной из дисциплин горнолыжного спорта: слаломе. Трасса строится с помощью установки ряда ворот, которые формируются двумя стойками. Лыжник должен пройти между двумя стойками, образующими каждые ворота. Победителем становится тот, кто затратит наименьшее время на прохождение трассы, не пропустив ни одних ворот.
Вы недавно начали учиться кататься на лыжах, но уже поставили перед собой цель принять участие в Зимних Олимпийских играх 2018 года, для которых Мадрид, возможно, представит свою кандидатуру. В рамках теоретической подготовки вам нужно написать программу, которая вычисляет минимальную длину пути, начиная с заданной точки и проходя через все ворота, пока вы не достигнете последних, которые являются финишной линией. Вы можете предположить, что ворота расположены горизонтально и упорядочены от самых высоких к самым низким, так что вам нужно проходить через них по порядку. Вы считаете себя опытным лыжником, поэтому можете выполнять любые серии поворотов, какими бы сложными они ни были, и ваша единственная задача — минимизировать общую длину пути.
Входные данные
Первая строка каждого случая содержит количество ворот n (1 ≤ n ≤ 1 000). Следующая строка содержит два числа с плавающей запятой, декартовы координаты x и y начальной позиции, в этом порядке. Далее следуют n строк, каждая из которых содержит три числа с плавающей запятой, y x_1 x_2, что означает, что следующие ворота — это горизонтальная линия от (x_1, y) до (x_2, y). Вы можете быть уверены, что x_1 < x_2. Значения y строго убывают и всегда меньше, чем у начальной позиции. Последние ворота представляют собой финишную линию. Все координаты находятся в пределах от −500 000 до 500 000 включительно. Значение 0 для n означает конец ввода. После каждого случая следует пустая строка.
Выходные данные
Для каждого тестового случая выведите строку с минимальным расстоянием, необходимым для достижения финишной линии. Ваш ответ должен быть точным в пределах абсолютной или относительной ошибки 10^{−7}.