• Зарегистрирован: 2010-02-24
  • Сообщений: 19

Тема: Лыжная трасса

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

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

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Лыжная трасса

N<=4? O_o
Вообще эту задачу можно решать для гораздо больших N, до 1000 где-то я знаю решение.

Динамика: считаем, что в любом оптимальном решении достаточно рассматривать только стартовую и конечную точку, и концы ворот. Соответственно, состояние динамики - это любая из этих точек, а значение динамики - длина кратчайшего пути от стартовой точки до текущей. Переходы - перебираем, куда мы переходим: в левый конец следующих ворот, в правый, и т.д. Переход каждый можно делать за O(1), если поддерживать текущий сектор видимости (т.е. два полярных угла, между которыми мы можем проехать по прямой). Итого за N^2 решение.

Ну при таких ограничениях-то, как у Вас, понятно, можно гораздо проще решение smile

Сайтe-maxx

3 Ответ от lanamelach

  • Зарегистрирован: 2010-02-24
  • Сообщений: 19

Re: Лыжная трасса

Может, я Вас неправильно понял, но, по-моему, предложенный подход позволит найти кратчайший путь, если лыжнику разрешается пересекать ворота только в начальной или конечной точке. В нашем случае он может пересекать их где-угодно, более того, он не обязательно должен делать повороты именно на линии пересечения с воротами, а может пересечь их и проехать дальше по прямой, а потом в произвольном месте повернуть в направлении других ворот (хотя я пока не нашел случая, где бы такое поведение было разумным).

4 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Лыжная трасса

Нет, пересекать разрешается где угодно, и поворачивать тоже. Но утверждение такое - что поворачивать есть смысл, только когда мы стоим в граничной точке ворот. И в таком решении мы тоже некоторые ворота будем пересекать где-то посередине, но фишка в том, что мы из одного состояния, в котором мы стоим в границе вороты, перебираем переход в одну из ворот ниже, в которой мы тоже встаем в одну из граничных точек (а вот ворота между этими двумя, получается, мы можем пересекать где-то посередине).

Сайтe-maxx