Description

When designing air routes, safety is a crucial concern. First, the most important thing is to take every measure to ensure that no accident occurs during flight. At the same time, we must also prepare for the worst: if an accident happens, passengers should have the highest possible chance of survival.

When a plane makes an emergency landing on the sea, the nearest land becomes a key factor. The most dangerous location along a route is the point that is farthest from the nearest land; we call such a point the route’s “isolation point.” The distance from the isolation point to the closest land is called the “isolation distance.” As a senior consultant for an airline, your first task is to find a route’s isolation point as best as possible and compute this route’s isolation distance.

To simplify the problem, we consider the map as a 2D plane, land masses are approximated by polygons, and the flight route is a polyline. The start and end points of the route lie on land, but intermediate turning points may be on the sea (as shown in the figure below; the grid marks the isolation point).

Input Format

The first line contains two integers $C$ and $N$ ($1 \le C \le 20$, $2 \le N \le 20$), representing the number of land masses and the number of turning points of the route, respectively.

Then there are $N$ lines, each containing two integers $x, y$. The pair $(x, y)$ is the coordinate of a turning point of the route. The first turning point is the start of the route, and the last turning point is the end of the route.

The next part of the input describes the $C$ land masses. Each land mass starts with a positive integer $M$ ($M \le 30$), the number of vertices of the polygon. The following $M$ lines each contain two integers $x, y$, which are the coordinates of a polygon vertex. We guarantee that these vertices are given in clockwise or counterclockwise order and form a simple closed polygon (no edges intersect). We also guarantee that any two land masses do not intersect.

All coordinates are within the range from −10,000 to 10,000.

Output Format

Output a floating-point number representing the route’s “isolation distance,” rounded to exactly 2 decimal places.

1 2
-9 -6
5 1
3
0 16
-16 -12
17 -6

0.00

2 3
12 4
16 17
3 9
4
1 0
4 19
19 14
6 12
3
10 10
5 3
18 2

2.94

Hint

For 50% of the testdata, $1 \le C \le 2$, $2 \le N \le 5$.
For 100% of the testdata, $1 \le C \le 20$, $2 \le N \le 20$.

Translated by ChatGPT 5