Problem Background

Members of the HURRICANE team recently went to a factory for an internship and encountered the following problem during their internship. They need to cut a part from a template. Both the template and the part are given convex polygons, and the position of the part within the template is fixed. It is known that for the part, except for adjacent sides, the intersection point of the extension lines of any two sides is outside the template.

Due to the limitations of the factory's processing conditions, each cut must be made along a straight line that coincides with one of the part's edges, dividing the template into two parts, and then retaining the part that contains the part, and continuing to cut. The cost of each cut is defined as the length of the cut on the template. The question is how to choose the cutting order to minimize the cost.

Problem Description

Your program needs to provide output based on the given input:

• The input includes the shapes and coordinates of the template and the part;
• You need to calculate the minimum cost to cut the template into the part based on the given input;
• The output should include only one number, which is the minimum cost rounded to the nearest integer.

Input and Output Formats

Input Format

The input file includes two parts, describing the shapes and coordinates of the template and the part:

• The first line is the number of vertices of the template, n (3 ≤ n ≤ 2000). The next n lines each contain two real numbers x, y (-1,000,000 < x, y < 1,000,000), representing the coordinates of the template vertices in counterclockwise order.
• The n+2nd line is the number of vertices of the part, m (3 ≤ m ≤ 2000). The next m lines each contain two real numbers x, y (-1,000,000 < x, y < 1,000,000), representing the coordinates of the part vertices in counterclockwise order.

Output Format

The output file should include only one integer, which is the minimum cost rounded to the nearest integer.

Sample Input and Output

Sample Input #1

4
0 0
3 0
3 3
0 3
4
1 1
2 1
2 2
1 2

Sample Output #1

8

Sample Input #2

4
0 0
3 0
3 3
0 3
4
0 0
2 0
2 3
0 3

Sample Output #2

3

见题面 Input 部分

见题面 Output 部分