← 返回题目列表

Codeforces · 75/E

E. 船舶的最短路径

中文机器翻译题面 查看原题

你找到了一份新工作,而且很有趣,你是一名船长。您的第一个任务是将您的船从一个点移动到另一个点,并且您肯定希望以最小的成本将其移动。

众所周知,任意两点之间的最短距离是这两点之间的线段的长度。但不幸的是,海上有一个岛屿,所以有时你无法在两点之间的线段上移动你的船。

你只能移动到安全点。如果一个点位于起点和终点之间的线段上,或者位于岛的边缘上,则该点被称为安全点。

但是你太幸运了,你有一些聪明又强大的工人,他们可以在你的旅途中帮助你,他们可以帮助你在海里移动船,他们会为海中的每个移动单位收取1埃及镑,他们可以搬运船(是的,他们非常强大)并在岛上行走,他们会为岛上的每个移动单位收取2埃及镑。你给他们的钱将在所有工人之间分配,所以工人的数量在这里并不重要。

你可以在岛边缘移动你的船,它将被视为在海中移动。

现在您有一张海洋地图,您必须确定您的旅行的最低成本是多少。

你的起点是(xStart, yStart),终点是(xEnd, yEnd),两个点会不同。

岛屿将是一个凸多边形,并且同一条线上的多边形点不会超过 2 个,并且起点和终点不会在岛屿内部或边界上。多边形的点将以逆时针顺序给出。

输入

第一行包含 4 个整数,xStart、yStart、xEnd 和 yEnd (- 100 ≤ xStart、yStart、xEnd、yEnd ≤ 100)。第二行包含一个整数n,它是多边形中的点数(3 ≤ n ≤ 30),后面的一行包含n对整数x和y,它们是点的坐标(- 100 ≤ x,y ≤ 100),多边形点将是不同的。

输出

打印一行,其中包含可能的最小成本。答案的绝对或相对误差不应超过 10 - 6。

示例

输入 #1

1 7 6 7
4
4 2 4 12 3 12 3 2

输出 #1

6.000000000

输入 #2

-1 0 2 0
4
0 0 1 0 1 1 0 1

输出 #2

3.000000000