Bridges
Two convex polygons are given, each initially having N vertices. One polygon is positioned entirely above the OX axis, while the other is entirely below it. Vertices are removed one by one from these polygons.
Before each removal and after the final removal, you need to determine the length of the shortest segment that can connect a vertex from the first polygon to a vertex from the second polygon. This segment must not intersect the interior of either polygon.
Input
The first line contains the integer N (3 ≤ N ≤ 100000), representing the number of vertices in each polygon. The next N lines each contain two integers: x_i, y_i (-1000000000 ≤ x_{i }≤ 1000000000, 1 ≤ y_{i }≤ 1000000000), which are the coordinates of the vertices of the first polygon.
Following this, there are N lines, each with two integers: x_i, y_i (-1000000000 ≤ x_{i }≤ 1000000000, -1000000000 ≤ y_{i }≤ -1), representing the coordinates of the vertices of the second polygon. The vertices of both polygons are listed in counterclockwise order. It is guaranteed that no two vertices coincide, and no three vertices of a single polygon are collinear. Then, 2N-2 lines follow, each containing two integers: n_j and v_j (1 ≤ n_j ≤ 2, 1 ≤ v_j ≤ N), indicating that vertex number v_j from the n_j-th polygon should be removed. It is guaranteed that no vertex will be removed more than once, and that after 2N-2 removals, exactly one vertex will remain in each polygon.
Output
Output 2N-1 lines, each containing one real number d_j — the minimal length of the segment connecting the vertices of the two polygons without passing through the interior of the polygons. d_j corresponds to the length of the required segment before the j-th removal, and d_{2N-1} corresponds to the length of the required segment after all removals. All lengths must be accurate to an absolute or relative error of 10^{-8}.