2281. Crossing, Touching or Overlapping
Two closed segments AB and CD are given. Say HOW they meet, with one of four
words.
APART they have no point in common
CROSS exactly one common point, lying strictly inside both segments
TOUCH exactly one common point, which is an endpoint of at least one of them
OVERLAP infinitely many common points
(0,0)-(4,0) and (2,-2)-(2,2) -> CROSS
(0,0)-(4,0) and (4,0)-(8,0) -> TOUCH
(0,0)-(4,0) and (2,0)-(6,0) -> OVERLAP
(0,0)-(4,0) and (5,0)-(8,0) -> APART
The four words are exhaustive and mutually exclusive, because a common point set
of two segments is empty, a single point, or a sub-segment. When it is a single
point, either it is an endpoint of one of them or it is interior to both, never
neither. A zero-length segment is a single point which is both of its own
endpoints, so when it meets anything at all the answer is TOUCH.
## What most people try first
A yes-or-no intersection routine with a bit bolted on. That ordering causes the
trouble: the straddle test answers YES for a proper crossing and NO for
everything that involves a zero determinant, so the three interesting classes
all arrive down the same branch and have to be told apart afterwards anyway.
The second common attempt computes the intersection point and compares it with
the four endpoints. The point is a ratio, so this is where floating point gets
in, and it cannot describe OVERLAP at all, because there is no single point to
compute.
## Decide from the four signs, in this order
d1 = cross(A,B,C) d2 = cross(A,B,D)
d3 = cross(C,D,A) d4 = cross(C,D,B)
If all four are zero the four points lie on one line. Then project the four
endpoints onto the direction of the longer segment with a dot product, which is
an integer, and compare the two spans: no overlap means APART, a single shared
value means TOUCH, and a span of positive length means OVERLAP.
Otherwise the segments are not collinear, so they share at most one point. Ask
the ordinary question first: if they do not meet, APART. If they do, the
answer is CROSS exactly when all four determinants are non-zero, because a
zero determinant is precisely the statement that an endpoint lies on the other
segment's line, and an endpoint of the shared point makes it TOUCH.
That ordering matters: testing for CROSS before handling the all-zero case
would classify two identical segments as a crossing.
## 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.
The projection used in the collinear branch is a dot product of two differences,
so it is also bounded by 8 * 10^12 and needs the same 64-bit type.
Constraints - `1 <= q <= 100000` - `-1000000 <= ax, ay, bx, by, cx, cy, dx, dy <= 1000000` - a segment may have zero length; such a segment is a single point and is both of its own endpoints
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 exactly one of the words APART, CROSS, TOUCH or OVERLAP on its own line, 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.