Bug2#2259

Bug2

3 секунди

256 мегабайтів

Складна

Існує багато навігаційних задач навколо нас. Це задача про алгоритм під назвою Bug2.

Bug-алгоритми розв'язують таку навігаційну задачу. Дано двовимірну карту з перешкодами довільної форми, а також початкову і кінцеву точки. Також є агент, який спочатку знаходиться у точці $S$ , і його завдання — дістатися у точку фінішу $F$ . Він знає координати фінішної точки, і в будь-який момент часу може визначити власні координати. Агент має $O (1)$ пам'яті, тому не може зберігати карту перешкод. Єдиний спосіб отримати інформацію про зовнішній світ — це визначати, чи торкається він перешкоди. Агент здатен рухатися навколо перешкоди, слідуючи по її межі. Задача полягає в тому, щоб дістатися фінішної точки, якщо це можливо, і коректно повідомити про недосяжність в іншому випадку.

Алгоритм Bug2, який належить до сімейства Bug-алгоритмів, працює так:

1. Рухатися в напрямку $F$ , поки не відбудеться одна з наступних подій:

Досягнута фінішна точка. Тоді алгоритм зупиняється.
Виявлено перешкоду. Тоді перейти до кроку 2.

2. Визначити поточну точку як $H$ . Рухатися по межі перешкоди за годинниковою стрілкою, поки не відбудеться одна з наступних подій:

Досягнута фінішна точка. Тоді алгоритм зупиняється.
Досягнута точка $H$ . Тоді фініш недосяжний і алгоритм зупиняється.
Досягнута точка $L$ , яка лежить на прямій $SF$ , $∣ LF ∣ < ∣ HF ∣$ |\textbf{LF}| < |\textbf{HF}| і можливо рухатися в напрямку $F$ , не натрапляючи одразу на перешкоду. У цьому разі перейти до кроку 1.

Можна довести коректність алгоритму: тобто, він досягає фінішної точки за скінченний час (тобто, довжина отриманого шляху скінчена), якщо це можливо, і повідомляє про недосяжність фінішу також за скінченний час.

Дано набір багатокутних перешкод, а також початкову і фінішну точку. Визначте довжину шляху, який пройде агент під керуванням алгоритму Bug2.

Вхідні дані

У першому рядку вхідного файлу записано п'ять цілих чисел $n$ , $x_{S}$ x_S, $y_{S}$ y_S, $x_{F}$ x_F, $y_{F}$ y_F — кількість перешкод та координати початкової і фінішної точок.

Далі у вхідному файлі описуються перешкоди. Кожен опис починається з рядка з одним цілим числом $m$ ( $m \geq 3$ m \ge 3) — кількість вершин у перешкоді. Наступні $m$ рядків містять пари цілих чисел $x_{i}$ x_i, $y_{i}$ y_i — координати вершин перешкоди, подані за годинниковою стрілкою. Перешкода не має самоперетинань або самонадкриттів.

Загальна кількість вершин усіх перешкод не перевищує $300000$ . Жодна координата за модулем не перевищує $1 0^{6}$ 10^6.

Жодна вершина перешкоди не лежить на прямій $SF$ . Обидві точки старту та фінішу лежать строго поза всіма перешкодами. Жодні дві перешкоди не мають спільних точок. Якщо існують дві точки $A$ і $B$ , де межі перешкод перетинають пряму $SF$ , то виконується або $∣ AF ∣ = ∣ BF ∣$ |\textbf{AF}| = |\textbf{BF}|, або $∣∣ AF ∣ - ∣ BF ∣∣ > 1 0^{- 6}$ ||\textbf{AF}|-|\textbf{BF}|| > 10^{-6}.

Вихідні дані

Виведіть довжину шляху, що проходить агент під керуванням описаного алгоритму. Допускається абсолютна або відносна похибка $1 0^{- 6}$ 10^{-6}.

Приклади

Приклад 1