Maximum Boundary Contact

Two puzzle pieces are given as simple polygons. The pieces represent separate components of a wooden puzzle. The goal is to place the two pieces by a rigid transformation (translation and rotation only, no reflection or scaling) such that their interiors do not overlap but their boundaries touch and the length of the common touching boundary is maximized.

It turns out that in an optimal placement the contact occurs along (portions of) one edge from each polygon. Assume that the polygons are given by a list of vertices. One piece is given in counterclockwise (CCW) order while the other is given in clockwise (CW) order. For a polygon given in CCW order, the interior lies to the left of a directed edge; for a polygon in CW order the interior lies to the right of a directed edge.

When aligning an edge from the CCW polygon with an edge from the CW polygon, the rigid transformation (rotation and translation) can be chosen so that the two edges are collinear with the same direction. In that configuration the interior half‐planes of the two pieces (with respect to the common line) are exactly opposite, ensuring that the interiors do not overlap. The maximum possible contact along that pair of edges is then min(L₁, L₂), where L₁ and L₂ are the lengths of the two edges.

Your task is to compute the maximum possible common boundary length over all pairs of edges, one from each polygon, that can be aligned in the described manner. If no pair of edges can be aligned (i.e. no pair has the same direction), the answer is 0.

Input/Output details: The first polygon is given with n vertices and the second polygon with m vertices. The vertices are listed with their x and y coordinates. You may assume that the first polygon is given in CCW order and the second in CW order, so that a valid alignment requires the selected edges to have the same unit direction. (Two unit vectors are considered the same if their dot product is at least 1 − 10⁻⁹.)

Input Format:
The first line contains an integer n (number of vertices of the first polygon). The following n lines each contain two real numbers representing the coordinates of the vertices in order.
Then a line with an integer m is given, followed by m lines each with two real numbers for the second polygon’s vertices.

Output Format:
Output a single real number, rounded and displayed to 6 decimal places: the maximum possible length of the common boundary that can be achieved.

inputFormat

Input begins with an integer n (3 ≤ n ≤ 10⁵), the number of vertices of the first polygon, followed by n lines each containing two real numbers representing the x and y coordinates of the vertices, given in counterclockwise order.

Then an integer m (3 ≤ m ≤ 10⁵) is given, followed by m lines each with two real numbers for the second polygon’s vertices, given in clockwise order.

outputFormat

Output a single real number: the maximum possible length of the common boundary (to 6 decimal places) that can be obtained by a valid placement.

sample

4
0 0
1 0
1 1
0 1
4
0 0
0 1
1 1
1 0

1.000000