题目描述

在二维平面上，有一个凸多边形 $C$，其有 $N$ 个顶点，以及两个点 $S=(s_x, s_y)$ 和 $T=(t_x, t_y)$。多边形 $C$ 的顶点按逆时针顺序为 $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$。保证点 $S$ 和 $T$ 都在多边形外部，且不在边界上。

求从点 $S$ 到点 $T$ 的最短路径长度，要求路径不能进入多边形 $C$ 的内部，但允许在多边形 $C$ 的边界上移动。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个整数 $x_i, y_i$，表示多边形的一个顶点。

接下来一行两个整数 $s_x, s_y$，表示起点 $S$ 的坐标。

最后一行两个整数 $t_x, t_y$，表示终点 $T$ 的坐标。

输出格式

输出一个浮点数，表示最短路径长度。

你的输出被认为正确，如果与真实值的绝对误差或相对误差不超过 $10^{-6}$。

样例

样例输入 1：

4
1 1
3 1
3 3
1 3
0 2
5 2

样例输出 1：

5.65028153987288474496

样例解释 1：

一种可行的最短路径是 $(0,2) \rightarrow (1,3) \rightarrow (3,3) \rightarrow (5,2)$，路径长度约为 $5.650281\dots$。可以证明这是最小值。注意路径可以经过多边形的边界。

你的输出只要误差在 $10^{-6}$ 以内即视为正确，例如输出 $5.650287$ 也被接受。 样例输入 2：

3
0 0
2 0
1 10
3 7
10 3

样例输出 2：

8.06225774829854965279

数据范围

• $3 \le N \le 10^5$
• $|x_i|, |y_i|, |s_x|, |s_y|, |t_x|, |t_y| \le 10^9$
• 输入保证 $(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)$ 按逆时针顺序构成一个凸多边形。
• 多边形任意三个顶点不共线。
• 点 $S$ 和 $T$ 在多边形外部且不在边界上。
• 输入中的所有值都是整数。