Alice and Bomb#3308

Alice and Bomb

30 seconds

256 megabytes

Easy

Alice is in the city when she suddenly discovers a suspicious-looking bag lying nearby. The bag starts emitting a ticking sound, and Alice fears it may contain a bomb. Fortunately, the bomb has not exploded yet, and there may be just enough time for Alice to run and take cover behind a building.

The ACM city can be modeled as an infinite plane where each building is represented by a polygon. Alice is considered as a point. The blast from the possible explosion may reach Alice if the straight line segment connecting Alice and the bomb does not cross through the interior of any building. Assume that the bomb's blast propagates infinitely fast: when the explosion occurs, its blast wave will reach any place immediately, unless its path is blocked by buildings.

The figure below illustrates a scenario of a bomb blast. The left figure shows the bomb and the buildings (the black-filled polygons). The right figure marks the area (shaded in gray) that is affected by the blast wave after the explosion.

Figure 1: Example of a bomb explosion

Note that even if the segment connecting Alice and the bomb only touches the boundary of a building, the blast can still reach Alice. Since Alice wants to escape as quickly as possible, she wants to minimize the distance she must run to be safely hidden behind a building.

Your task is to write a program that, given the positions of Alice, the suspicious bag (bomb), and the buildings, calculates the minimum distance Alice must run to take cover behind a building.

Input

The input contains multiple test cases. Each test case has the following format:

$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}

The first line of each test case contains an integer $N$ ( $1 \leq N \leq 100$ 1 \le N \le 100), denoting the number of buildings. The second line contains two integers $b x$ and $b y$ ( $- 10000 \leq b x, b y \leq 10000$ -10000 \le bx, by \le 10000), denoting the location of the bomb. Then, $N$ lines follow, each describing a building.

Each building is given as a polygon defined by its corner points. Each line contains an integer $m_{i}$ m_i ( $3 \leq m_{i} \leq 100$ 3 \le m_i \le 100, $m_{i} \leq 500$ m_i \le 500), which is the number of the polygon's corners, followed by $m_{i}$ m_i pairs of integers $x_{i, j}$ x_{i,j}, $y_{i, j}$ y_{i,j} representing the coordinates of the points.

You may assume that

Polygons do not intersect themselves.
No two polygons share a common point.
The point sets are provided in counterclockwise order.
The initial positions of Alice and the bomb are not inside any polygon.
The bomb is not located on any of the infinitely extended lines of any polygon edge.

Alice's initial position is $(0, 0)$ . It is possible that Alice is initially located on the border of a polygon.

$N = 0$ N = 0 denotes the end of the input. You should not process this as a test case.

Output

For each test case, output one line with the minimum distance Alice must run to take cover behind a building. An absolute or relative error less than $1 0^{- 6}$ 10^{-6} is permitted in your answer.

Examples

Example 1