← 返回题目列表

Codeforces · 1628/F

F. 宇宙飞船危机管理

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

NASA(挪威宇航员物品协会)正在开发一种新的宇宙飞船转向系统。但在目前的状态下,如果飞船最终陷入一堆太空垃圾中,那就不太安全了。为了确保转向系统安全,他们需要回答以下问题:

给定目标位置 $$$t = (0, 0)$$$,由线段 $$$l_i = ((a_{ix}, a_{iy}), (b_{ix}, b_{iy}))$$$ 描述的一组 $$$n$$$ 块太空垃圾 $$$l$$$,以及起始位置 $$$s = (s_x, s_y)$$$,是否有一个方向,从起始位置朝那个方向浮动会到达目标位置?

当飞船撞上一块太空垃圾时,会发生什么取决于漂浮方向与线段之间的角度绝对差$$$\theta$$$:

- 如果$$$\theta < 45^{\circ}$$$,飞船沿着这块太空垃圾以最小化角度变化的方向滑动,当飞船滑出太空垃圾的末端时,它继续沿它来时的方向漂浮(在撞到太空垃圾之前)。
- 如果$$$\theta \ge 45^{\circ}$$$,宇宙飞船会停止,因为沿着太空垃圾滑动的摩擦力太大。

你只会得到一组太空垃圾一次,目标位置始终是 $$$(0, 0)$$$,但有 $$$q$$$ 查询,每个查询都有一个起始位置 $$$s_j = (s_{jx}, s_{jy})$$$。

针对每个查询回答上述问题。

输入

第一行包含整数 $$$n$$$ ($$$1 \le n \le 1500$$$)。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含 $$$4$$$ 整数 $$$a_{ix}$$$、$$$a_{iy}$$$、$$$b_{ix}$$$ 和 $$$b_{iy}$$$ ($$$|a_{ix}|, |a_{iy}|, |b_{ix}|, |b_{iy}| \le 1000$$$)。

接下来是包含整数 $$$q$$$ ($$$1 \le q \le 1000$$$) 的行。

接下来是 $$$q$$$ 行,其中第 $$$j$$$ 行包含 $$$2$$$ 整数 $$$s_{jx}$$$ 和 $$$s_{jy}$$$ ($$$|s_{jx}|, |s_{jy}| \le 1000$$$)。

保证 $$$l$$$ 中的任何段都不会交叉或接触,$$$t$$$ 不在 $$$l$$$ 中的任何段上,$$$s_j$$$ 不在 $$$l$$$ 中的任何段上,并且 $$$s \neq t$$$。

输出

对于每个查询 $$$s_j$$$ 打印一个答案。如果存在一个方向,使得从 $$$s_j$$$ 朝该方向浮动,可能沿着某些太空垃圾滑动,导致 $$$t$$$,则打印“YES”。否则,打印“NO”(不区分大小写)。

示例

输入 #1

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

输出 #1

YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
YES

注意

蓝色十字代表目标位置,其他蓝色线段代表太空垃圾。

绿点代表答案为“是”的起始位置,红点代表答案为“否”的起始位置。

黄线是第 $$$3$$$rd 和第 $$$14$$$ 查询到目标位置的可能路径。

黑线是从第$$$6$$$查询中的起始位置开始的可能路径,但它几乎没有错过目标位置。