ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102939
Тема:    [ Вычислительная геометрия (прочее) ]
Сложность: 3
Классы:
Название задачи: SOS .
В корзину
Прислать комментарий

Условие

В океане в точке с координатами (X, Y) потерпел крушение корабль. Недалеко от места катастрофы находится остров, имеющий форму N-угольника (не обязательно выпуклого). Спасшиеся после кораблекрушения пассажиры оказались в спасательной шлюпке, которая может двигаться относительно воды в любом направлении со скоростью, не превосходящей V. В процессе движения шлюпка может менять как направление, так и величину своей скорости.

В океане имеется постоянное течение, вектор скорости которого – (VTx, VTy). Тем самым, вектор скорости шлюпки относительно земли определяется как сумма вектора скорости течения (VTx, VTy) и вектора скорости шлюпки относительно воды (Vx, Vy).

Требуется найти минимальное время, за которое шлюпка сможет добраться до острова, либо определить, что из-за сильного течения это невозможно.

Входные данные

Входной файл содержит (в указанном порядке) следующие данные: координаты (X, Y) места крушения, количество вершин острова N (3 ≤ N ≤ 50), координаты вершин острова, заданные в порядке обхода острова по часовой стрелке (2N чисел), максимальную скорость спасательной шлюпки V (V > 0) и вектор скорости течения (VTx, VTy). Все числа во входном файле, кроме N, являются вещественными и разделяются пробелами и/или символами перевода строки.

Выходные данные

Выведите в выходной файл искомое время не менее чем с 6 верными значащими цифрами. Если шлюпка до острова доплыть не сможет, выходной файл должен содержать сообщение «добраться невозможно». 

Пример входного файла

4 3
3
0 0 0 3 3 0
2 1 1

Пример выходного файла

4.828427

Решение

Скачать архив тестов и решений

Геометрическое место точек, где может оказаться шлюпка через время t, представляет собой расширяющийся круг радиуса V·t, плывущий по
направлению течения со скоростью (VTx, VTy). Нас интересует первый момент времени, в который этот круг коснется заданного N-угольника. Ясно, что он может коснуться либо его вершины, либо его стороны. Первый случай соответствует высадке людей из шлюпки в вершине острова, второй – на стороне острова. Понятно, что для минимизации времени шлюпка должна плыть с максимальной собственной скоростью V не меняя направления движения.

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

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

Тем самым, для решения задачи необходимо рассмотреть все возможные варианты высадки и выбрать тот из них, который минимизирует затрачиваемое время.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 4
Название Вычислительная геометрия
Задача
Номер 9

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .