0373. Облако

Константин Константинович Константинопольский – ученый-метеоролог. Недавно он увлекся строительством летательных аппаратов и построил радиоуправляемый зонд для исследования кучевых облаков.

Для исследования облака Константин Константинович поднимает аппарат в воздух, направляет его полёт параллельно поверхности Земли (поскольку высота небольшая, Землю можно считать плоской), после чего ориентирует аппарат таким образом, чтобы он пролетел сквозь облако по прямой линии. Константин Константинович понимает, что пока аппарат находится внутри облака, менять его курс рискованно, поскольку облако может исказить управляющие сигналы с пульта.

Так как качество исследования облака напрямую зависит от количества собранных данных, Константин Константинович хочет узнать, сколько времени аппарат проведёт в полёте внутри облака.

Для упрощения задачи Константин Константинович считает поверхность Земли плоской, а облако представляет в виде многоугольника на плоскости (необязательно выпуклого). Поскольку аппарат сравнительно мал, Константин Константинович считает его материальной точкой с некоторым заданным изначально направлением движения. Вам требуется по координатам точек многоугольника-облака, начальным координатам аппарата и вектору его скорости определить, какой путь аппарат проведёт внутри облака. При этом путь по границе облака учитывать не нужно.

Формат входного файла

В первой строке входного файла задано одно число N – количество вершин в многоугольнике, описывающем облако (1 ≤ N ≤ 100). Далее в N строках расположено по два числа x_i, y_i – координаты i-той вершины многоугольника (в порядке обхода). После этого в одной строке задается четыре числа x₀, y₀, v_x, v_y – координаты начального положения аппарата и его вектора скорости. Все координаты являются вещественными числами, не более чем с тремя знаками после десятичной точки. Все координаты не превосходят 1000 по модулю.

Формат выходного файла

Выведите единственное число – длину пути, которую аппарат проведёт внутри облака. Ваш ответ будет считаться корректным, если абсолютная или относительная погрешность ответа будет не более 10^-5.

Пример:

В примере 2 иллюстрируется условие, что путь по границе облака учитывать не нужно.

В примере 3 демонстрируется, что путь аппарата в облаке может состоять из нескольких отрезков.

Источник: Открытый весенний чемпионат ПетрГУ по программированию, 20 апреля 2014

Обсудить       Отправить решение



Версия для печати