P4534 [CTSC2004] Optimal Cutting

Members of the HURRICANE team recently went to a factory for an internship and encountered the following problem during the process.

The HURRICANE team needs to cut out a part from within a template. Both the template and the part are given convex polygons, and the position of the part inside the template is fixed. For the part, for any two non-adjacent edges, the intersection point of the extensions of their supporting lines lies outside the template. Due to factory constraints, each cut must follow the straight line containing some edge of the part, splitting the template into two pieces. Keep the piece that contains the part and continue cutting. The cost of each cut is the length of the cut mark on the template. You need to compute the minimum total cost required to cut out the part.

The first line contains a positive integer $n$, the number of vertices of the template. The next $n$ lines each contain two real numbers $x, y$, giving the coordinates of the template’s vertices listed in counterclockwise order. The $(n+2)$-th line contains a positive integer $m$, the number of vertices of the part. The next $m$ lines each contain two real numbers $x, y$, giving the coordinates of the part’s vertices listed in counterclockwise order.

Output a single integer, which is the minimum total cost rounded to the nearest integer.

For $100\%$ of the testdata, it is guaranteed that $3 \le n, m \le 2000$ and $|x|, |y| \le 10^9$. Translated by ChatGPT 5