Spaceship Crisis Management

题意翻译

### 题目描述 现有一艘飞船要从 $s=(s_x,s_y)$ 处行驶到 $t=(0,0)$ 处。但是在太空中有 $n$ 块太空垃圾，每块都可以看做一条线段，用其两个端点的坐标 $l_i = ((a_{i_x},a_{i_y}),(b_{i_x},b_{i,y}))$ 表示。飞船撞上太空垃圾的移动轨迹取决于飞行路径和表示这块太空垃圾的线段的绝对角度差 $\theta$（个人理解是两条线段相交形成的较小的角的角度）： - 若 $\theta<45^\circ$：太空飞船会旋转最小角度使飞行方向平行太空垃圾，并沿着太空垃圾滑动，到了垃圾末尾再沿撞上前的飞行方向继续前进； - 若 $\theta\ge 45^\circ$：飞船会立刻停止运动。 给出 $n$ 块太空垃圾的坐标，固定终点为 $t=(0,0)$，给出 $q$ 个起点 $s_j=(s_{j_x},s_{j_y})$。对于每个起点，输出“YES”或“NO”表示能否确定一个飞行方向使得飞船能从起点到达终点。 ### 输入格式及数据范围 第一行 1 个整数 $n$ 表示太空垃圾的块数（$1\le n\le1500$）； 接下来 $n$ 行每行 4 个正整数，第 $i$ 行的 $a_{i_x},a_{i_y},b_{i_x},b_{i_y}$ 描述第 $i$ 块太空垃圾（$\left|a_{i_x}\right|,\left|a_{i_y}\right|,\left|b_{i_x}\right|,\left|b_{i_y}\right|\le 1000$）； 接下来一行 1 个整数 q，表示起点的个数（$1\le q\le 1000$）； 接下来 $q$ 行每行 2 个正整数，第 $j$ 行的 $s_{j_x},s_{j_y}$ 描述第 $j$ 个起点（$\left|s_{j_x}\right|,\left|s_{j_y}\right|\le 1000$）。 数据保证没有两块太空垃圾相交或接触，终点 $t$ 不在太空垃圾上，没有起点 $s_j$ 在太空垃圾上，且没有起点 $s_j = t$。 ### 样例解释 如图，蓝色叉为终点 $t$ ，绿色和红色的点为输入的起点，其中绿色的为有可行方向的（即输出“YES”的），红色的为没有的。 黄色路径为点 (0,10) 和 (3,-2) 的一种可行路径，黑色的是 (3,10) 的一种最佳路径——非常接近终点但是仍不能到达，所以这个点是不可行的。

题目描述

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 < 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.

输入输出格式

输入格式

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 $ .

输出格式

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).

输入输出样例

输入样例 #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

说明

 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.