Беглый Домино
"Эффект домино" — это популярная игра с использованием домино. Игрок выстраивает цепочку из стоящих домино. Когда цепочка завершена, игрок опрокидывает одно домино на конце цепочки. Первое домино опрокидывает второе, второе — третье, и так далее.
Вы играете в эффект домино. Однако, прежде чем вы успели закончить выстраивать цепочку, одно из домино начало падать. Ваша задача — как можно быстрее остановить это падение.
Цепочка домино образует ломаную линию на плоскости в двумерной системе координат и не пересекается сама с собой. Падение начинается с определенной точки на цепочке и распространяется в обоих направлениях. Если падение начинается с конца цепочки, оно продолжается в противоположном направлении. Падение в направлении останавливается, когда вы касаетесь точки падения или когда оно достигает конца цепочки.
Вы можете предположить следующее:
Вы — это точка без объема в двумерной системе координат.
Падение останавливается сразу после касания точки падения.
Вы можете пересекать цепочку домино, не вызывая её падения.
Вам будет дана форма цепочки домино, начальная точка падения, ваши координаты в момент начала падения, скорость падения и ваша скорость. Ваша задача — написать программу, которая вычисляет ваше оптимальное движение для остановки падения в кратчайшие сроки и определяет минимальное время для этого.
Входные данные
Первая строка содержит одно целое число N (2 ≤ N ≤ 1000), обозначающее количество вершин в ломаной линии цепочки домино. Далее следуют N строк, каждая из которых содержит два целых числа x_i и y_i, обозначающих координаты i-й вершины (-10000 ≤ x_i, y_i ≤ 10000). Следующая строка содержит три целых числа x_t, y_t и v_t, которые обозначают координаты начальной точки падения и скорость падения. Последняя строка содержит три целых числа x_p, y_p и v_p, которые обозначают ваши координаты в момент начала падения и вашу скорость (1 ≤ v_t < v_p ≤ 10). Вы можете предположить, что начальная точка падения лежит на ломаной линии.
Выходные данные
Выведите минимальное время для остановки падения. Результат должен иметь относительную или абсолютную погрешность менее 10^{-6}.