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$$$查询中的起始位置开始的可能路径,但它几乎没有错过目标位置。