|
Название задачи: 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 не меняя направления движения.
В случае высадки в вершине острова скорость шлюпки относительно земли должна быть направлена на данную вершину. Надо учесть, что, в общем случае, не до всех вершин можно доплыть, так как при малой собственной скорости шлюпки рассматриваемый круг может проплыть мимо них.
В случае высадки на стороне острова необходимо направить собственную скорость шлюпки перпендикулярно данной стороне (покажите это!). Здесь возможен случай, что шлюпку снесет течением, и она пройдет мимо этой стороны острова. В таком случае вариант высадки на этой стороне не рассматривается.
Тем самым, для решения задачи необходимо рассмотреть все возможные варианты высадки и выбрать тот из них, который минимизирует затрачиваемое время.
