Алиса и Бомба
Алиса и Боб когда-то были влюблены, но теперь они ненавидят друг друга.
Однажды Алиса нашла сумку, похожую на ту, что Боб носил, когда они встречались. Вдруг она услышала звук тикания. Алиса сразу подумала, что Боб хочет убить её с помощью бомбы. К счастью, бомба ещё не взорвалась, и, возможно, у неё есть немного времени, чтобы спрятаться за зданиями.
Город 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}.