eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

Жук2

Лимит времени 3 секунды
Лимит использования памяти 256 MiB

Вокруг нас существует большое количество задач на навигацию. Эта задача про алгоритм, который называется Жук2.

Жук-алгоритмы решают следующую навигационную задачу. Имеется двумерная карта, содержащая препятствия произвольной формы, а также старт и финиш. Имеется "агент", который стоит в начальной точке S, и его задача состоит в том, чтобы добраться до конечной точки F. Он знает координаты конечной точки, и в любой момент времени может определить свои координаты. Агент имеет O(1) памяти, поэтому не может хранить карту препятствий. Информацию о внешнем мире он может получить, лишь определив касается ли он препятствия. Агент может двигаться вдоль препятствий, следуя по их границам. Задача агента состоит в том чтобы достичь финиш или сообщить что это сделать невозможно.

Алгоритм Жук2, который принадлежит множеству Жук-алгоритмов, работает следующим образом:

1. Двигаемся к F пока не будет иметь место одно из следующих условий:

  • Достигнута конечная точка. Алгоритм останавливается.

  • Встретили препятствие. Переходим на шаг 2.

2. Обозначим текущую точку через H. Двигаемся вокруг препятствия по часовой стрелке пока не будет иметь место одно из условий:

  • Достигнута конечная точка. Алгоритм останавливается.

  • Достигнута точка H. Тогда конечная точка не достижима. Алгоритм останавливается.

  • Достигнута точка L, которая лежит на прямой SF, |LF| < |HF| и при этом можно двигаться по направлению к F, не попав сразу в препятствие. В этом случаее переходим к шагу 1.

Можно доказать корректность алгоритма. То есть тот факт, что агент либо достигнет конечной точки за конечное время (длина результирующего пути конечна), либо сообщит, что конечная точка не достижима за конечное время.

По заданному множеству препятствий, а также координатам начальной и конечной точки, следует определить длину пути, который пройдет агент согласно алгоритма Жук2.

Входные данные

Первая строка содержит пять целых чисел n, x_S, y_S, x_F, y_F - количество препятствий и координаты начальной и конечной точки.

Остальная часть входных данных описывает препятствия. Описание каждого препятствия начинается с количества вершин m (m 3) в нем. Следующие m строк описывают целочисленные координаты x_i, y_i вершин препятствий в порядке их обхода по часовой стрелке. Препятствие не имеет самопересечений и самокасаний.

Общее количество вершин во всех препятствиях не превосходит 300000. Ни одна из координат по модулю не больше 10^6.

Ни одна вершина препятствия не лежит на прямой SF. Начальная и конечная точка лежат строго вне препятствий. Никакие два препятствия не имеют общей точки. Для любых двух точек A и B, в которых препятствия пересекают прямую SF, выполняется либо |AF| = |BF|, либо ||AF| - |BF|| > 10^{-6}.

Выходные данные

Вывести длину пути, пройденного агентом согласно описанного алгоритма. Допускается ошибка порядка 10^{-6}.

Пример

Входные данные #1
1 0 2 6 2
8
1 0
1 3
2 3
2 1
4 1
4 3
5 3
5 0
Выходные данные #1
10.0