409867: GYM103811 K Kario Mart

A new supermarket "Kario Mart" has opened in the neighbourhood! As a promotion event to attract customers, the supermarket is giving out 1000 dollars coupon to the first customer who completes a lap around the supermarket while pushing a shopping trolley.

The layout of Kario Mart can be described by two simple polygons, $$$P_1$$$, $$$P_2$$$, of $$$N$$$ and $$$M$$$ vertices respectively, where $$$P_1$$$ is fully enclosed by $$$P_2$$$. Also, $$$P_1$$$ and $$$P_2$$$ do not touch. The area of the Kario Mart is the area covered in $$$P_2$$$ that is not covered by $$$P_1$$$. For example, the red region in the following diagram is the walkable region.

A complete lap in the market is defined as a sequence of points $$$p_1, p_2, ..., p_k$$$ that forms a simple polygon that fully encloses $$$P_1$$$. The lap can start at any point in the market. The following diagram shows an example of a lap.

As a broke student, you would like to win the event at all costs. Write a program to find the length of the shortest possible lap.

The first line consists of two integers, $$$N$$$ and $$$M$$$ $$$(3 \leq N, M \leq 100)$$$, the number of vertices of $$$P_1$$$ and $$$P_2$$$ respectively.

The following $$$N$$$ lines contains $$$N$$$ pairs of integer $$$(x, y)$$$ representing the coordinates of vertices of $$$P_1$$$ in clockwise order.

The final $$$M$$$ lines contains $$$M$$$ pairs of integer $$$(x, y)$$$ representing the coordinates of vertices of $$$P_2$$$ in clockwise order.

For all input coordinates $$$(x, y)$$$, $$$0 \leq |x|, |y| \leq 5000$$$.

For each polygon:

• There are no duplicate vertices.
• Exactly 2 line segments meet at each vertex.
• No angle is a multiple of 180 degrees.

The output consists of one floating point number, the minimum length of the lap. Your output should have an absolute error or relative error of at most $$$10^{-6}$$$.

6 4
1 7
7 7
5 3
7 1
1 1
3 5
0 0
0 8
8 8
8 0

24.0

6 5
1 7
7 7
5 3
7 1
1 1
3 5
0 0
0 8
8 8
6 3
8 0

24.359174

Sample 2 corresponds to the example in the problem statement.