Главная > SOS
1995
Имя входного файла: input.txt
Имя выходного файла: output.txt

В океане, в точке с координатами (x, y) потерпел крушение корабль. Недалеко от места крушения находится остров, который имеет форму N-угольника (многоугольник не обязательно выпуклый; 3 < N < 50). Спасшиеся после кораблекрушения пассажиры оказались в шлюпке, которая может двигаться в любом направлении со скоростью, не превосходящей v (v > 0; шлюпка может менять направление и величину скорости во время движения; скорость v задана относительно воды). В океане имеется постоянное течение, вектор скорости которого (vtx, vty). Требуется найти минимальное время, за которое шлюпка доберется до острова, либо определить, что из-за сильного течения шлюпка до острова доплыть не сможет.


Формат входных данных

Первое число в файле задает количество наборов исходных данных. Набор содержит координаты места крушения (x, y); количество вершин острова N; координаты вершин острова, заданные в порядке обхода острова по часовой стрелке: x1, y1, x2, y2, ..., xN, yN; максимальную скорость спасательной шлюпки v; вектор скорости течения (vty, vtx). Все числа в исходном файле разделяются пробелами и (или) символами перевода строки. Координаты и скорости задаются вещественными числами.


Формат выходных данных

Для каждого набора исходных данных вывести в выходной файл на отдельной строке минимальное время, за которое спасательная шлюпка может добраться до острова, либо сообщение "добраться невозможно".


Примечания

  1. Все величины задаются в одой системе измерения.
  2. Минимальное время в ответе должно быть верно с точностью до 3-х знаков после запятой.
  3. Напомним вам, что вектор скорости шлюпки относительно земли находится как сумма вектора скорости течения (vtx, vty) и вектора скорости шлюпки относительно воды (vx, vy). Поскольку шлюпка может двигаться в любом направлении со скоростью, не превосходящей v, то длина вектора (vx, vy) не должна превышать v, т.е. vx2+ vy2v2.


Пример

input.txtoutput.txt
2
5.2 7.65 3 0 0 0 3 3 0 2.5 17.8 0
4 3 3 0 0 0 3 3 0 2 1 1
добраться невозможно
4.828427

 
Hosted by uCoz