WoW 2. В следующее измерение!

Задача
Две землеройки постоянно находятся на спине питона в точках [latex]A[/latex] и [latex]C[/latex]. Однако, по неизвестной причине в момент времени [latex]t_A[/latex] первая землеройка отправляется в пункт [latex]B[/latex] с расчётным временем прибытия [latex]t_B[/latex]. Поскольку такое поведения является характерным для землероек вообще, вторая поступила также и в момент времени [latex]t_C[/latex] отправилась в пункт [latex]D[/latex] с расчётным временем прибытия [latex]t_D[/latex]. На новом месте землеройки в дальнейшем планирует находиться постоянно. Известно, что землеройки обычно движутся по питонам с постоянной скоростью стараясь держаться центра спины, чтобы не соскальзывать. Питоны же во время движения землероек спокойно лежат без самопересечений.
Дано:
Точки [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], [latex]D[/latex] задаются расстоянием от кончика хвоста питона, измеренным вдоль обычного маршрута землероек. Время старта и прибытия землероек также задано. Входные данные задаются целыми числами не превосходящими по модулю 10000 в следующем формате:

A t_A
B t_B
C t_C
D t_D

Найти:
Необходимо определить, удастся ли землеройкам проделать этот маневр или в результате столкновения они свалятся с питона. Если питону удастся избавиться от докучливых землероек выведите “Yes”, в противном питону случае – “No”.

Тесты

A B C D Результат Комментарий
i 0 10000 0 10000 Yes Пересечение крест-накрест
t_i 0 10000 10000 0
i -1 1 2 3 No Нет общего интервала значений по оси абсцисс
t_i -1 1 2 3
i 0 1 1 0 Yes Столкновение движущейся и покоящейся землероек
t_i 0 1 1 3

Код программы:

Анализ. Формализация задачи.
Название задачи намекает на построение графика зависимости координаты от времени:
Промежутки неподвижности землероек обозначены на данном графике вертикальными линиями, движения — наклонными.
При таком подходе задачу можно свести к конкретной математической проблеме: определить, пересекает ли отрезок, не параллельный оси ординат, ломаную.
Алгоритм решения.

  1. Определить, имеют ли ломаные общий интервал значений по оси абсцисс. Если его нет, то пересечься они не могут. Проверку по оси ординат проводить не нужно, т.к. вертикальные участки ломаных не ограничены сверху.
  2. Составить шесть общих уравнений прямых, проходящих через две заданные точки.
    [latex]\frac {y-y1}{y2-y1} = \frac {x-x1}{x2-x1}[/latex].
    То же самое, что и:
    [latex] (y_{1} — y_{2})x + (x_{2} — x_{1})y + (x_{1}y_{2} — x_{2}y_{1}) = 0[/latex]. (*)
  3. По свойству общего уравнения прямой, при подстановке точки в уравнение (*) возможны три случая: полученное значение меньше, больше или равно нулю. Соответственно, точка либо лежит в левой или правой полуплоскостях, либо она лежит на прямой. Если при подстановке концов отрезка получим значения разных знаков, то отрезок пересекает прямую.
  4. Пересечься землеройки могут в двух случаях:
    1. Когда первая движется, а вторая — нет.
    2. Когда они движутся одновременно.

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

Детали реализации:
Для определения, пересекаются ли отрезок и ломаная или нет, использована булева функция. Для поиска максимума двух чисел использована функция swap из заголовочного файла algorithm.
Корректность работы алгоритма, определяющего, пересекаются ли два отрезка, заданные координатами своих концов, подтверждают пройденные тесты на сайте e-olimp: http://www.e-olimp.com/solutions/1597737
Протестировать решение можно по ссылке: http://ideone.com/FjdLoO
Решение на Java: http://ideone.com/AxLzPh

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

3 thoughts on “WoW 2. В следующее измерение!

  1. Хорошо, но…
    — Ссылки в самом конце лучше делать именно как ссылки.
    — В таблицах всё куда-то уехало.
    — Условные операторы почему-то излишне сдвигаются
    — Нумерованные списки (ordered list) задаётся командой OL. Отдельные пункты списка — (list item) LI

    • Ваши замечания учтены и исправлены, за исключением разметки таблиц: на локальной машине она отображается корректно, при вставке на сайт же правый столбец уезжает по неочевидной для меня причине. На следующем занятии я покажу вам исходный код записи, может, я уже не вижу, в чем там фатальный недостаток.

Добавить комментарий