Тема: Лыжная трасса
На лыжной трассе есть несколько ворот, через которые проезжают лыжники. Ворота можна проходить только в том порядке, в котором они заданы на входе. Объезжать ворота не разрешается. Считается, что траектория лыжника представляет собой обычную ломаную, которая соответственно пересекает отрезки, образованные воротами. Кроме того, трасса построена таким образом, что части ломаной до и после пересечения в окрестности пересечения с воротами лежат в разных полуплоскостях относительно ворот.
Задано 1<=N<=4 - количество ворот на трассе, далее N строк по четыре целых числа - две пары координат X,Y концов ворот (ворота не вырождаются в точку и не пересекаются между собой). Далее заданы координаты стартовой позиции Sx, Sy и конечной позиции Fx, Fy, куда должен попасть лыжник после прохода всех ворот.
Требуется вывести число, округленное до 3-х знаков после запятой, - минимальную длину маршрута при заданных правилах.
Ограничения:
0 ? |X|, |Y|, |Sx|, |Sy|, |Fx|, |Fy| ? 1000
время 1 с, память 65 мб
Пример ввода:
2
4 3 9 3
-8 8 -13 8
0 0
0 23
пример вывода:
35.000