在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
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
输出 #1
2 5.6055512755 8.48528137422 4 -1
输入 #2
4 -10 -9 10 -9 10 9 -10 9 2 0 10 0 -10 -10 -10 -10 -10
输出 #2
200.9975124224 0
输入 #3
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
输出 #3
59.0857761929 103.2455532034 94.7213595500 101.5640991922 164.8528137424 94.3398113206
注意
示例输入/输出#1 的说明
该示例如下图所示。
在$$$1$$$和$$$4$$$场景中,可以不改变方向直接到达终点。
在场景$$$2$$$中,你可以前往$$$(0, 2)$$$,然后改变方向到终点。
在场景$$$3$$$中,你可以前往$$$(6, 2)$$$,然后改变方向到终点。
在场景$$$5$$$中,可以表明不可能到达终点。