你找到了一份新工作,而且很有趣,你是一名船长。您的第一个任务是将您的船从一个点移动到另一个点,并且您肯定希望以最小的成本将其移动。
众所周知,任意两点之间的最短距离是这两点之间的线段的长度。但不幸的是,海上有一个岛屿,所以有时你无法在两点之间的线段上移动你的船。
你只能移动到安全点。如果一个点位于起点和终点之间的线段上,或者位于岛的边缘上,则该点被称为安全点。
但是你太幸运了,你有一些聪明又强大的工人,他们可以在你的旅途中帮助你,他们可以帮助你在海里移动船,他们会为海中的每个移动单位收取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