P14851 [ICPC 2022 Yokohama R] Traveling Salesperson in an Island
题目描述
你是岛上某个港口的销售员。你需要拜访岛上的所有港口，然后返回起始港口。因为你不会游泳且害怕大海，所以在旅途中必须停留在陆地上。
该岛被建模为二维平面上的一个多边形。该多边形是 **简单的**，即其顶点互不相同，且除相邻边在其公共顶点处相接外，没有两条边相交或相触。此外，没有两条相邻边共线。岛上的每个港口被建模为多边形边界上的一个点。你的路线被建模为一条不超出多边形范围的闭合曲线。
为了准备这次旅程，你想计算拜访所有港口并返回起始港口的最短路线长度。
输入格式
输入由单个测试用例组成，格式如下。
$$
\begin{aligned}
&n \ m \\
&x_1 \ y_1 \\
&\vdots \\
&x_n \ y_n \\
&x'_1 \ y'_1 \\
&\vdots \\
&x'_m \ y'_m
\end{aligned}
$$
第一行包含两个整数 $n$ 和 $m$，满足 $3 \leq n \leq 100$ 和 $2 \leq m \leq 100$。其中 $n$ 是建模岛屿的多边形的顶点数，$m$ 是岛上的港口数量。接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，是多边形第 $i$ 个顶点的坐标，其中 $0 \leq x_i \leq 1000$ 且 $0 \leq y_i \leq 1000$。多边形的顶点按逆时针顺序给出。接下来的 $m$ 行，每行包含两个整数 $x'_j$ 和 $y'_j$，是第 $j$ 个港口的坐标。路线从 $(x'_1, y'_1)$ 开始并结束。保证所有港口都位于多边形的边界上且互不相同。
输出格式
在一行中输出拜访所有港口并返回起始港口的最短路线长度。输出的相对误差必须在 $10^{-6}$ 以内。
说明/提示
这些样例如下图所示。最短路线用粗线表示。灰色多边形代表岛屿。小圆盘代表岛上的港口。注意，路线不一定非得是简单的，即路线可以自相交或重叠，如第二个样例中，两个港口之间的同一条路径被使用了两次。
:::align{center}
图 J.1. 样例 1
图 J.2. 样例 2
:::