CF1906D Spaceship Exploration

在 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}$ 时，视为正确。

样例输入输出 #1 说明 该样例如下图所示。  在场景 $1$ 和 $4$ 中，你可以直接到达终点，无需改变方向。 在场景 $2$ 中，你可以先到 $(0, 2)$，然后改变方向前往终点。 在场景 $3$ 中，你可以先到 $(6, 2)$，然后改变方向前往终点。 在场景 $5$ 中，可以证明无法到达终点。 由 ChatGPT 4.1 翻译