CF75E Ship's Shortest Path

你找到了一份新工作，非常有趣——你成为了一名船长。你的第一个任务是将你的船从一个点移动到另一个点，当然你希望以最小的代价完成这个任务。 众所周知，任意两个点之间的最短距离是这两个点之间线段的长度。但不幸的是，海上有一个岛屿，所以有时候你无法沿着两点之间的直线路径航行。 你只能移动到**安全点**。一个点被称为安全的，当且仅当它在起点和终点之间的线段上，或在岛屿的边界上。 不过你很幸运，你拥有一些聪明且强壮的工人，他们可以在旅途中协助你。他们可以帮助你在海上推动船只，这部分每移动一个单位花费 1 埃镑；他们也可以抬着船穿过岛屿，每移动一个单位花费 2 埃镑。由于工人之间会分摊这笔费用，所以工人的数量在这里并不重要。 你可以在岛屿的边界上移动船只，这将被视为在海上移动。 现在你有一张海图，你需要决定从起点到终点最小的行程花费。 起点为 $$(xStart, yStart)$$，终点为 $$(xEnd, yEnd)$$，这两个点不同。 岛屿是一个**凸多边形**，且任意一条直线上不会有超过两个多边形顶点。此外，起点和终点不会在岛屿的内部或边界上。多边形的顶点按逆时针顺序给出。

第一行包含 4 个整数： $$xStart, \ yStart, \ xEnd, \ yEnd$$ 其中 $$-100 \le xStart, yStart, xEnd, yEnd \le 100$$。 第二行包含一个整数 $$n$$，表示多边形顶点的数量（$$3 \le n \le 30$$）， 接下来一行包含 $$n$$ 对整数 $$(x, y)$$，表示多边形的顶点坐标，满足 $$-100 \le x, y \le 100$$，所有顶点彼此不同。

输出一行，表示最小可能的花费。 答案的绝对或相对误差不超过 $$10^{-6}$$。

翻译由 GPT-4o 提供。