CF1906D.Spaceship Exploration

In The ICPC Galaxy, there exists a zone filled with asteroids that is unsafe to enter. The map of the galaxy is represented in a 2D Cartesian coordinate system. The zone is in the shape of an $N$-sided convex polygon. Each corner is numbered from $1$ to $N$; corner $i$ is located at $(X_i, Y_i)$. At any moment, you should not be inside this polygon; however, it is safe to touch the side of the polygon.

There are $Q$ scenarios (numbered from $1$ to $Q$). In scenario $j$, you want to go from a starting point at $(A_j, B_j)$ to an ending point at $(C_j, D_j)$. You will be riding on a special spaceship that can only travel in a straight line. First, you set the direction of the spaceship, then the spaceship will start traveling in that direction. During the travel, you are only allowed to change direction at most once. Changing direction means you stop the spaceship, set a new direction, and then start traveling again in the new direction.

For each scenario, determine the minimum distance required to travel without being inside of the zone at any moment, or report if it is impossible to reach the ending point.

在 ICPC 星系中，存在一个充满小行星的危险区域，不可进入。星系的地图以二维笛卡尔坐标系表示。该危险区域呈 $N$ 边凸多边形形状。各顶点编号为 $1$ 至 $N$；其中顶点 $i$ 位于 $(X_i, Y_i)$。在任意时刻，你均不得位于该多边形内部；但允许恰好接触多边形的边界（即边）。

共有 $Q$ 个场景（编号为 $1$ 至 $Q$）。在场景 $j$ 中，你需要从起点 $(A_j, B_j)$ 出发，抵达终点 $(C_j, D_j)$。你将乘坐一艘特殊飞船，该飞船仅能沿直线航行。首先，你设定飞船的航行方向，随后飞船即沿该方向开始航行。在航行过程中，你最多允许改变一次方向；所谓“改变方向”是指：先使飞船停止，再设定新的航行方向，然后重新启动飞船沿新方向航行。

对每个场景，请确定在全程不进入危险区域（即始终不在多边形内部）的前提下，所需的最短航行距离；若无法抵达终点，则报告为不可能。

The first line consists of an integer $N$ ($3 \leq N \leq 100\,000$).

Each of the next $N$ lines consists of two integers $X_i$ $Y_i$ ($-10^9 \leq X_i, Y_i \leq 10^9$). The points form a convex polygon in counterclockwise order. There are no three points which are collinear.

The following line consists of an integer $Q$ ($1 \leq Q \leq 100\,000$).

Each of the next $Q$ lines consists of four integers $A_j$ $B_j$ $C_j$ $D_j$ ($-10^9 \leq A_j, B_j, C_j, D_j \leq 10^9$). There are no starting points and ending points inside the zone. However, it is possible for the starting point and the ending point to be at the side of the zone.

All the coordinates in the input are integers.

第一行包含一个整数 $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$）。所有线段的起点和终点均不在区域内部；但起点或终点可能恰好位于区域的边界上。

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

For each scenario, output the answer in a single line.

If it is possible to reach the ending point without being inside the zone at any moment, then output the minimum distance required to travel. Otherwise, output -1.

Your answer is considered correct if its absolute error or relative error does not exceed $10^{-6}$. Namely, if your answer is $a$ and the jury's answer is $b$, then your answer is accepted if $\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$.

对于每种情况，请在一行内输出答案。

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

当且仅当你的答案的绝对误差或相对误差不超过 $10^{-6}$ 时，该答案被视为正确。即：若你的答案为 $a$，评测机的标准答案为 $b$，则当 $\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$ 时，你的答案被接受。

Explanation for the sample input/output #1

This sample is depicted in the following illustration.

During scenario $1$ and $4$, you can directly go to the ending point without changing the direction.

During scenario $2$, you can go to $(0, 2)$, then change direction to the ending point.

During scenario $3$, you can go to $(6, 2)$, then change direction to the ending point.

During scenario $5$, it can be shown that it is impossible to reach the ending point.

样例输入/输出 #1 的说明

该样例如下图所示。

在情形 $1$ 和 $4$ 中，你可以不改变方向直接到达终点。

在情形 $2$ 中，你可以先到达点 $(0, 2)$，然后改变方向驶向终点。

在情形 $3$ 中，你可以先到达点 $(6, 2)$，然后改变方向驶向终点。

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