Аліса і Бомба
Аліса і Боб колись були закохані, але тепер вони ненавидять один одного.
Одного дня Аліса знайшла сумку, яка нагадала їй про ті, що Боб носив на їхні побачення. Раптом вона почула звук "тік-так". Інтуїція підказала їй, що Боб хоче вбити її за допомогою бомби. На щастя, бомба ще не вибухнула, і, можливо, у неї є трохи часу, щоб сховатися за будівлями.
Місто ACM можна уявити як нескінченну площину, де кожна будівля представлена багатокутником. Аліса вважається точкою, і вибух бомби може досягти її, якщо відрізок, що з'єднує Алісу і бомбу, не перетинає внутрішню частину жодної будівлі. Припустимо, що швидкість вибуху бомби нескінченна; коли бомба вибухає, її вибухова хвиля миттєво досягає будь-якого місця, якщо тільки шлях не перекритий будівлями.
На малюнку нижче показано приклад вибуху бомби. Лівий малюнок демонструє бомбу і будівлі (багатокутники, заповнені чорним). Правий малюнок показує область (заштрихована сірим), яка знаходиться під впливом вибухової хвилі після вибуху бомби.
Рисунок 1: Приклад вибуху бомби
Зверніть увагу, що навіть якщо відрізок, що з'єднує Алісу і бомбу, торкається межі будівлі, вибух бомби все одно може вразити Алісу. Оскільки Аліса хоче втекти якомога швидше, вона прагне мінімізувати відстань, яку їй потрібно пробігти, щоб сховатися за будівлею.
Ваше завдання - написати програму, яка зчитує позиції Аліси, бомби та будівель і обчислює мінімальну відстань, яку потрібно пробігти Алісі, щоб сховатися за будівлею.
Вхідні дані
Вхідні дані містять кілька тестових випадків. Кожен тестовий випадок має наступний формат:
N bx by m_1 x_{1,1} y_{1,1} ... x_{1,m1} y_{1,m1} ... m_N x_{N,1} y_{N,1} ... x_{N,mN} y_{N,mN}
Перша стрічка кожного тестового випадку містить ціле число N (1 ≤ N ≤ 100), яке позначає кількість будівель. У другій стрічці є два цілі числа bx і by (−10000 ≤ bx, by ≤ 10000), які означають розташування бомби. Потім слідують N рядків, що вказують інформацію про будівлі.
Інформація про будівлю надається у вигляді багатокутника, що складається з точок. Для кожного рядка є ціле число m_i (3 ≤ m_i ≤ 100, m_i ≤ 500), що означає кількість точок у багатокутнику, а потім слідують m_i пар цілих чисел x_{i,j}, y_{i,j}, що надають координати x і y точки.
Ви можете припустити, що
багатокутник не має самоперетинів.
жодні два багатокутники не мають спільної точки.
набір точок подано у проти годинникової стрілки.
початкові позиції Аліси і бомби не будуть розташовані всередині багатокутника.
немає бомби на жодній з продовжених ліній сегмента даного багатокутника.
Аліса спочатку знаходиться в точці (0, 0). Можливо, що Аліса знаходиться на межі багатокутника.
N = 0 позначає кінець введення. Ви не повинні обробляти це як тестовий випадок.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що складається з мінімальної відстані, яку потрібно пробігти Алісі, щоб сховатися за будівлею. Абсолютна або відносна похибка у вашій відповіді має бути меншою за 10^{−6}.