Spaceship Crisis Management
Contest: Codeforces Round 767 (Div. 1)
Difficulty rating: 3500
Tags: binary search, data structures, geometry, sortings

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.

Input format:
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$$$.

Output format:
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).

Constraints:
Time limit: 8.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
YES

Editorial:
The exit position at a specific segment is always the same, only the exit direction changes depending on which angle the spaceship comes in at. Therefore, if we know the set of directions that are good to hit a segment at, we know if a path that hits the segment is good or not. Note that it's only useful to consider directions that are either the direction from the closest point on some segment to the target, or from some starting position to the target. Let's call these directions relevant directions.
Slow solution: We can use DP to determine the set of useful directions for each segment: Sort the segments by distance to the target, and for each segment try shooting a ray in every relevant direction that is within 45 degrees of the direction of the segment itself, and see if it either hits the target or a segment where that direction is good. The comparison with 45 degrees can be done exactly using e.g. properties of the dot product. Then for each starting position query, the same ray shooting can be done. This is $$$O((n+q)^2 \cdot n)$$$ because there are $$$O(n+q)$$$ relevant directions, $$$O(n+q)$$$ positions from which to shoot rays, and $$$O(n)$$$ segments to check intersection with. This is too slow.
We found two different ways to optimize this:
1. Since we need to know what a ray hits for many different directions from the same origin, we could do some preprocessing at each origin. A Li-Chao tree traditionally finds the minimum y-value at a certain x-coordinate among a set of line segments. But it doesn't have to contain line segments. It can contain any set of functions such that any pair of them intersect at most once. This includes distance to 2D line segments from a fixed origin as a function of angle. Using this, we can for each origin do $$$O(n \cdot log (n+q))$$$ time precomputation to get $$$O(log (n+q))$$$ time per query to a single direction, resulting in the time complexity $$$O((n+q)^2 \log (n+q))$$$
2. Solution by Maksim1744: If we fix the floating direction, the movement between space junk forms edges in a functional graph. We can use a sweep to build the graph and then for each starting position and determine if it reaches the target in the graph. Doing this for all relevant directions also results in a time a complexity of $$$O((n+q)^2 \log (n+q))$$$