CF1628F.Spaceship Crisis Management

NASA (Norwegian Astronaut Stuff Association) is developing a new steering system for spaceships. But in its current state, it wouldn't be very safe if the spaceship would end up in a bunch of space junk. To make the steering system safe, they need to answer the following:

Given the target position $t = (0, 0)$, a set of $n$ pieces of space junk $l$ described by line segments $l_i = ((a_{ix}, a_{iy}), (b_{ix}, b_{iy}))$, and a starting position $s = (s_x, s_y)$, is there a direction such that floating in that direction from the starting position would lead to the target position?

When the spaceship hits a piece of space junk, what happens depends on the absolute difference in angle between the floating direction and the line segment, $\theta$:

• If $\theta \lt 45^{\circ}$, the spaceship slides along the piece of space junk in the direction that minimizes the change in angle, and when the spaceship slides off the end of the space junk, it continues floating in the direction it came in (before hitting the space junk).
• If $\theta \ge 45^{\circ}$, the spaceship stops, because there is too much friction to slide along the space junk.

You are only given the set of pieces of space junk once, and the target position is always $(0, 0)$, but there are $q$ queries, each with a starting position $s_j = (s_{jx}, s_{jy})$.

Answer the above question for each query.

美国国家航空航天局（挪威宇航员装备协会，NASA）正在为宇宙飞船开发一种新型转向系统。但目前该系统尚不安全：若飞船意外进入一片太空垃圾区域，则可能引发危险。为确保转向系统安全，需解决如下问题：

给定目标位置 $t = (0, 0)$、由 $n$ 段线段构成的太空垃圾集合 $l$，其中第 $i$ 段线段为 $l_i = ((a_{ix}, a_{iy}), (b_{ix}, b_{iy}))$，以及起始位置 $s = (s_x, s_y)$，是否存在某个方向，使得飞船从起始位置沿该方向自由漂浮，最终可抵达目标位置？

当飞船撞击某块太空垃圾时，其后续行为取决于漂浮方向与该线段之间的夹角绝对值 $\theta$：

• 若 $\theta \lt 45^{\circ}$，飞船将沿该太空垃圾线段滑动，滑动方向为使角度变化最小的方向；当飞船滑出线段端点后，继续以撞击前的原始方向漂浮；
• 若 $\theta \ge 45^{\circ}$，飞船将停止运动，因为此时摩擦力过大，无法沿太空垃圾滑动。

你仅被给定一次太空垃圾集合，且目标位置恒为 $(0, 0)$；但共有 $q$ 个查询，每个查询给出一个起始位置 $s_j = (s_{jx}, s_{jy})$。

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

The first line contains the the integer $n$ ($1 \le n \le 1500$).

Then follows $n$ lines, the $i$-th of which containing the $4$ integers $a_{ix}$, $a_{iy}$, $b_{ix}$, and $b_{iy}$ ($|a_{ix}|, |a_{iy}|, |b_{ix}|, |b_{iy}| \le 1000$).

Then follows a line containing the integer $q$ ($1 \le q \le 1000$).

Then follows $q$ lines, the $j$-th of which containing the $2$ integers $s_{jx}$ and $s_{jy}$ ($|s_{jx}|, |s_{jy}| \le 1000$).

It is guaranteed that none of the segments in $l$ cross or touch, that $t$ is not on any segment in $l$, that $s_j$ is not on any segment in $l$, and that $s \neq t$.

第一行包含一个整数 $n$（$1 \le n \le 1500$）。

接下来是 $n$ 行，其中第 $i$ 行包含四个整数 $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$ 行包含两个整数 $s_{jx}$ 和 $s_{jy}$（满足 $|s_{jx}|, |s_{jy}| \le 1000$）。

保证：线段集合 $l$ 中任意两条线段均不相交也不接触；点 $t$ 不在 $l$ 的任意一条线段上；点 $s_j$ 不在 $l$ 的任意一条线段上；且 $s \neq t$。

For each query $s_j$ print an answer. If there exists a direction such that floating from $s_j$ in that direction, possibly sliding along some pieces of space junk, leads to $t$, print "YES". Otherwise, print "NO" (case insensitive).

对于每个查询 $s_j$，输出一个答案。如果存在某个方向，使得从 $s_j$ 沿该方向漂浮（过程中可能沿某些太空垃圾滑动）能够到达 $t$，则输出 "YES"；否则输出 "NO"（不区分大小写）。

The blue cross represents the target location, and the other blue line segments represent the space junk.

Green dots represent starting locations where the answer is yes, and red dots represent starting locations where the answer is no.

The yellow lines are possible paths to the target location for the $3$rd and $14$th queries.

The black line is a possible path from the starting location in the $6$th query, but it barely misses the target location.

蓝色十字表示目标位置，其余蓝色线段表示太空垃圾。

绿色圆点表示答案为“是”的起始位置，红色圆点表示答案为“否”的起始位置。

黄色线条表示第 3 次和第 14 次查询中通往目标位置的可能路径。

黑色线条表示第 6 次查询中从起始位置出发的一条可能路径，但它恰好未到达目标位置。