Аліса і Бомба#3308

Аліса і Бомба

30 секунд

256 мегабайтів

Легка

Аліса перебуває в місті, коли раптово помічає підозрілу сумку, що лежить поблизу. Сумка починає видавати тикаючий звук, і Аліса підозрює, що в ній може бути бомба. На щастя, бомба ще не вибухнула, і в Аліси, можливо, лишилося якраз досить часу, щоб утекти й сховатися за будівлею.

Місто ACM можна змоделювати як нескінченну площину, де кожна будівля представлена багатокутником. Аліса вважається точкою. Вибухова хвиля може досягти Аліси, якщо відрізок, що з'єднує Алісу й бомбу, не перетинає інтер'єру жодної будівлі. Припустимо, що вибухова хвиля бомби поширюється миттєво: коли відбувається вибух, його хвиля досягає будь-якого місця одразу, якщо її шлях не перекривають будівлі.

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

Рисунок 1: Приклад вибуху бомби

Зверніть увагу, що навіть якщо відрізок, що з'єднує Алісу й бомбу, лише торкається межі будівлі, вибухова хвиля все одно може дістатися до Аліси. Оскільки Аліса хоче втекти якнайшвидше, вона прагне мінімізувати відстань, яку їй потрібно пробігти, щоб безпечно сховатися за будівлею.

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

Вхідні дані

Вхід містить декілька тестових випадків. Кожен тестовий випадок має такий формат:

$N$ $b x$ $b y$ $m_{1}$ m_1 $x_{1, 1}$ x_{1,1} $y_{1, 1}$ y_{1,1} ... $x_{1, m_{1}}$ x_{1,m_1} $y_{1, m_{1}}$ y_{1,m_1} ... $m_{N}$ m_N $x_{N, 1}$ x_{N,1} $y_{N, 1}$ y_{N,1} ... $x_{N, m_{N}}$ x_{N,m_N} $y_{N, m_{N}}$ y_{N,m_N}

У першому рядку кожного тестового випадку подано ціле число $N$ ( $1 \leq N \leq 100$ 1 \le N \le 100) — кількість будівель. У другому рядку розташовано два цілих числа $b x$ і $b y$ ( $- 10000 \leq b x, b y \leq 10000$ -10000 \le bx, by \le 10000) — координати бомби. Далі йде $N$ рядків, кожен із яких описує окрему будівлю.

Кожна будівля описується як багатокутник, заданий своїми вершинами. Кожний із цих рядків містить ціле число $m_{i}$ m_i ( $3 \leq m_{i} \leq 100$ 3 \le m_i \le 100, $m_{i} \leq 500$ m_i \le 500) — кількість вершин багатокутника, далі йде $m_{i}$ m_i пар цілих чисел $x_{i, j}$ x_{i,j}, $y_{i, j}$ y_{i,j}, що задають координати вершин.

Можна вважати, що

Багатокутники не самоперетинаються.
Жодні два багатокутники не мають спільних точок.
Вершини багатокутників задані у проти-годинниковому порядку.
Початкові координати Аліси й бомби не лежать усередині жодного багатокутника.
Бомба не розташована на жодній з нескінченно продовжених сторін жодного багатокутника.

Початкова позиція Аліси — $(0, 0)$ . Можливо, Аліса спочатку перебуває на межі багатокутника.

$N = 0$ N = 0 означає кінець вхідних даних. Не потрібно обробляти цей випадок як тестовий.

Вихідні дані

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

Приклади

Приклад 1