题目描述

给定两个凸多边形 $A$ 和 $B$，保证 $B$ 严格位于 $A$ 的内部。

你想要通过一系列切割将 $B$ 从 $A$ 中分离出来。为此，每次你画一条完全穿过 $A$ 的直线，该直线经过 $B$ 的一条边，并将 $A$ 分成两部分。你沿着这条直线切割，并丢弃不包含 $B$ 的那一部分。重复这一过程，直到剩余的部分恰好就是 $B$。

:::align{center} :::

一次切割的成本等于该切割线的长度（即该直线在当前剩余 $A$ 内部被切割的长度）。给定 $A$ 和 $B$，求分离出 $B$ 所需的最小成本。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个测试用例的第一行包含一个整数 $a$（$3 \leq a \leq 200$），表示多边形 $A$ 的顶点数。接下来的 $a$ 行，每行包含两个整数 $x$ 和 $y$（$-10^6 \leq x, y \leq 10^6$），按顺时针顺序给出 $A$ 的顶点。保证 $A$ 是凸多边形。

下一行包含一个整数 $b$（$3 \leq b \leq 200$），表示多边形 $B$ 的顶点数。接下来的 $b$ 行，每行包含两个整数 $x$ 和 $y$（$-10^6 < x, y < 10^6$），按顺时针顺序给出 $B$ 的顶点。保证 $B$ 是凸多边形，并且 $B$ 完全位于 $A$ 的内部。

多边形内部或跨多边形之间没有三点共线。

输出格式

输出一个浮点数，表示将 $B$ 从 $A$ 中分离出来的最小成本。如果答案与标准答案的相对误差不超过 $10^{-6}$，则视为正确。

4
0 0
0 14
15 14
15 0
4
8 3
4 6
7 10
11 7

40.0000000000

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

322.1421356237

提示

翻译由 DeepSeek V3.2 完成