2280. Do Two Segments Meet
Two closed segments are given, AB and CD. Print YES if they have at least
one point in common and NO otherwise.
(0,0)-(4,0) and (2,-2)-(2,2) -> YES they cross
(0,0)-(4,0) and (2,1)-(2,2) -> NO the second stops short
(0,0)-(4,0) and (4,0)-(6,3) -> YES they touch at one endpoint
(0,0)-(4,0) and (2,0)-(6,0) -> YES they overlap along a stretch
## What most people try first
Solve for the intersection of the two infinite lines, then check that the solution lies within both segments. It works, and it is the version that goes wrong, for two reasons.
The intersection point is a RATIO, so the moment it is computed the arithmetic leaves the integers and the range checks become comparisons of rounded numbers. And the parallel case has to be split off anyway, because then the denominator is zero: two collinear segments may overlap, touch at an endpoint, or miss entirely, and the formula says nothing about which.
## The straddle test
AB and CD cross properly when each segment has the other's endpoints on
opposite sides. In signs:
``` d1 = cross(A,B,C) d2 = cross(A,B,D) d3 = cross(C,D,A) d4 = cross(C,D,B)
proper crossing <-> d1 and d2 have strictly opposite signs and d3 and d4 have strictly opposite signs ```
That is four integer determinants and no division at all. It is correct because
a segment separates the plane locally: if C is to the left of line AB and
D is to the right, the segment CD must pass through line AB somewhere, and
the symmetric statement pins that somewhere to within AB.
## Why four more tests are needed
The straddle test demands STRICTLY opposite signs, so it answers NO whenever
any of the four determinants is zero, and zero is exactly the interesting case:
an endpoint lying on the other segment. So add four on-segment checks, one per
endpoint against the other segment, using the collinear-plus-box test. Those
four also cover the whole collinear family, including a complete overlap, and
they cover a zero-length segment, which has no side at all and which the
straddle test can never report as meeting anything.
## Width
Coordinates satisfy |x|, |y| <= 1000000, so each coordinate difference is at most 2 * 10^6, each product of two differences at most 4 * 10^12, and a cross product at most 8 * 10^12 in magnitude. A signed 32-bit integer stops at 2147483647, so a 32-bit cross product wraps and reports the wrong SIGN, which is a wrong answer and not merely a wrong number. The value is below 2^53 = 9007199254740992, so a JavaScript Number holds it exactly and no BigInt is needed; the bitwise operators must not appear, because they coerce to 32 bits.
Constraints - `1 <= q <= 100000` - `-1000000 <= ax, ay, bx, by, cx, cy, dx, dy <= 1000000` - a segment may have zero length, that is `A` may equal `B` or `C` may equal `D`
Input
The first line contains an integer q.
Each of the next q lines contains eight integers ax ay bx by cx cy dx dy, the coordinates of A, B, C and D in that order, separated by spaces.
Output
For each query print YES on its own line if the two closed segments share at least one point, and NO otherwise. Print the words in upper case with nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.