← 返回题目列表

Codeforces · 1906/D

D. 宇宙飞船探索

中文机器翻译题面 查看原题

在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$$$中,可以表明不可能到达终点。