说明

在 ICPC 银河中，存在一个充满小行星的区域，进入该区域是不安全的。银河的地图用二维笛卡尔坐标系表示。该区域的形状是一个 $N$ 边的凸多边形。每个顶点编号为 $1$ 到 $N$，第 $i$ 个顶点的坐标为 $(X_i, Y_i)$。在任何时刻，你都不能处于该多边形内部；但是，接触多边形的边是安全的。

有 $Q$ 个场景（编号为 $1$ 到 $Q$）。在第 $j$ 个场景中，你需要从起点 $(A_j, B_j)$ 前往终点 $(C_j, D_j)$。你将驾驶一艘只能沿直线飞行的特殊飞船。首先，你设定飞船的方向，然后飞船会沿该方向前进。在飞行过程中，你最多只能改变一次方向。改变方向意味着你停下飞船，设定一个新方向，然后继续沿新方向前进。

对于每个场景，判断在任何时刻都不进入该区域的情况下，所需的最小飞行距离，或者报告无法到达终点。

输入格式

第一行包含一个整数 $N$（$3 \leq N \leq 100\,000$）。

接下来的 $N$ 行，每行包含两个整数 $X_i$ $Y_i$（$-10^9 \leq X_i, Y_i \leq 10^9$）。这些点按逆时针顺序组成一个凸多边形。不存在三点共线的情况。

接下来一行包含一个整数 $Q$（$1 \leq Q \leq 100\,000$）。

接下来的 $Q$ 行，每行包含四个整数 $A_j$ $B_j$ $C_j$ $D_j$（$-10^9 \leq A_j, B_j, C_j, D_j \leq 10^9$）。所有起点和终点都不在该区域内部，但可能在区域的边上。

所有输入的坐标均为整数。

输出格式

对于每个场景，输出一行答案。

如果可以在任何时刻都不进入该区域的情况下到达终点，则输出所需的最小飞行距离。否则输出 $-1$。

如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。即，如果你的答案为 $a$，标准答案为 $b$，则当 $\frac{|a-b|}{\max(1, |b|)} \leq 10^{-6}$ 时，视为正确。

5
0 2
2 0
4 0
4 4
2 4
5
6 1 6 3
2 5 0 0
3 5 3 -1
1 4 5 4
3 4 3 0

2
5.6055512755
8.48528137422
4
-1

4
-10 -9
10 -9
10 9
-10 9
2
0 10 0 -10
-10 -10 -10 -10

200.9975124224
0

8
-20 -10
10 -20
25 -15
35 -5
30 10
15 20
-25 15
-30 5
6
-15 -15 -15 20
-30 -5 30 15
25 20 -5 -20
-5 25 20 -20
-30 10 30 -10
-30 -50 50 0

59.0857761929
103.2455532034
94.7213595500
101.5640991922
164.8528137424
94.3398113206

提示

样例输入输出 #1 说明

该样例如下图所示。

:::align{center} :::

在场景 $1$ 和 $4$ 中，你可以直接到达终点，无需改变方向。

在场景 $2$ 中，你可以先到 $(0, 2)$，然后改变方向前往终点。

在场景 $3$ 中，你可以先到 $(6, 2)$，然后改变方向前往终点。

在场景 $5$ 中，可以证明无法到达终点。

由 ChatGPT 4.1 翻译