Cut It Out!
Time limit2sMemory limit512 MB
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 and . It is guaranteed that lies strictly inside .
You want to cut out of . Each cut is a straight line that passes completely through and runs along one edge of . The line splits into two pieces. You cut along it and discard the piece that does not contain . Repeat until the remaining piece is exactly .

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 . Given and , find the minimum cost to cut out.
Input
The first line contains an integer (), the number of vertices of . The next lines each contain two integers and , the vertices of in clockwise order. is guaranteed to be convex.
The next line contains an integer (), the number of vertices of . The next lines each contain two integers and , the vertices of in clockwise order. is guaranteed to be convex and to lie entirely inside . The coordinates of satisfy , and the coordinates of satisfy .
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 out of . The answer is accepted if its relative error is within of the judges' answer.