Polygonal Puzzle

At last year's ACM ICPC World Finals in Marrakesh, one of the judges bought a wooden puzzle that shows a camel and palm trees (Figure 1). A usual jigsaw puzzle is made by cutting up one finished rectangular picture, but every piece of this puzzle was cut and painted on its own. Neighbouring pieces often share no picture element and no colour, and the finished picture has an irregular outline. In a puzzle like this, the shape of a piece is often the only clue to where it belongs.

The judge has wondered ever since whether a program can solve this puzzle. Such a program needs a way to measure how well two pieces match. The better the match, the more likely the two pieces are neighbours in the puzzle.

Figure 1: the judge's wooden puzzle.

Pieces are modelled as simple polygons. Place the two given polygons so that their interiors do not overlap and their boundaries touch, and make the length of the common boundary as large as possible. You may translate and rotate the polygons, but you may not reflect or resize them.

The input describes two polygons, one after the other. The description of a polygon starts with a line holding the number of vertices $n$ ($3 \le n \le 50$). Each of the next $n$ lines holds the integer coordinates $x$ and $y$ ($|x|, |y| \le 100$) of one vertex. The vertices of each polygon are given in clockwise order, and no three consecutive vertices are collinear.

The input data is chosen so that moving the vertices by a distance of up to $10^{-7}$ would not increase the answer by more than $10^{-4}$.

Figure 2: the first example input and its optimal placement.

Print the largest possible length of the common boundary of the two polygons, rounded to exactly six digits after the decimal point.