Under construction

Still being built. Things may change

Cut It Out!

Time limit2sMemory limit512 MB

Summary
Given convex polygons A and B with B strictly inside A, find the minimum total length of cuts along B's edge lines that leave exactly B.
Level

Hard8 of 10

Topics
Geometry, Dynamic programming
Solved
No attempts yet

Problem

You are given two convex polygons AA and BB. It is guaranteed that BB lies strictly inside AA.

You want to cut BB out of AA. Each cut is a straight line that passes completely through AA and runs along one edge of BB. The line splits AA into two pieces. You cut along it and discard the piece that does not contain BB. Repeat until the remaining piece is exactly BB.

The cost of a cut is the length of the cut, that is, the length of the line segment that runs through the remaining part of AA. Given AA and BB, find the minimum cost to cut BB out.

Input

The first line contains an integer aa (3≤a≤2003 \le a \le 200), the number of vertices of AA. The next aa lines each contain two integers xx and yy, the vertices of AA in clockwise order. AA is guaranteed to be convex.

The next line contains an integer bb (3≤b≤2003 \le b \le 200), the number of vertices of BB. The next bb lines each contain two integers xx and yy, the vertices of BB in clockwise order. BB is guaranteed to be convex and to lie entirely inside AA. The coordinates of AA satisfy −106≤x,y≤106-10^6 \le x, y \le 10^6, and the coordinates of BB satisfy −106<x,y<106-10^6 < x, y < 10^6.

No three points are collinear, whether within one polygon or across both polygons.

Output

Print a single floating point number, the minimum cost to cut BB out of AA. The answer is accepted if its relative error is within 10−610^{-6} of the judges' answer.

Examples2

  1. Example 1

    Input
    4
    0 0
    0 14
    15 14
    15 0
    4
    8 3
    4 6
    7 10
    11 7
    
    Expected output
    40.0000000000
    
  2. Example 2

    Input
    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
    
    Expected output
    322.1421356237