SOS

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

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

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

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

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

Пример входного файла
4 3
3
0 0 0 3 3 0
2 1 1

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

Решение

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

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

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

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