#216191. [ICPC 2018 NAIPC] Cut It Out!

You are given two convex polygons and . It is guaranteed that is strictly contained inside of .

You would like to make a sequence of cuts to cut out from . To do this, you draw a straight line completely through that is incident to one of the edges of , which separates into two pieces. You cut along this line and discard the piece that doesn’t contain . You repeat this until the piece that you have left is exactly .

:::align{center} :::

The cost of making a cut is equal to the length of the cut (i.e. the length of the line through the remainder of ). Given and , find the minimum cost needed to cut out.

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line containing a single integer (), which is the number of points in polygon . Each of the next lines will contain two integers and (), which are the vertices of polygon , in clockwise order. It is guaranteed that polygon will be convex.

The next line will contain a single integer (), which is the number of points in polygon . Each of the next lines will contain two integers and (), which are the vertices of polygon , in clockwise order. It is guaranteed that polygon will be convex. It is also guaranteed that polygon will reside entirely within the interior of polygon .

No three points, within a polygon or across polygons, will be collinear.

Output a single floating point number, which is the minimum cost to cut out of . To be considered correct, this number must be within a relative error of of the judges’ answer.

样例输入 1

4
0 0
0 14
15 14
15 0
4
8 3
4 6
7 10
11 7

样例输出 1

40.0000000000

样例输入 2

4
-100 -100
-100 100
100 100
100 -100
8
-1 -2
-2 -1
-2 1
-1 2
1 2
2 1
2 -1
1 -2

样例输出 2

322.1421356237