Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.02.2010, 13:18
Lanamelach

 
Сообщений: n/a

Лыжник
На лыжной трассе есть несколько ворот, через которые проезжают лыжники. Ворота можна проходить только в том порядке, в котором они заданы на входе. Объезжать ворота не разрешается. Считается, что траектория лыжника представляет собой обычную ломаную, которая соответственно пересекает отрезки, образованные воротами. Кроме того, трасса построена таким образом, что части ломаной до и после пересечения в окрестности пересечения с воротами лежат в разных полуплоскостях относительно ворот.

Задано 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
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра