2314. Where Does the Perpendicular Foot Land
Drop a perpendicular from a point P onto the LINE through A and B. Print
BEFORE if the foot lands beyond A, away from B; AFTER if it lands beyond
B; and INSIDE if it lands on the closed segment AB. A foot landing exactly
on A or exactly on B counts as INSIDE. Answer q such queries, with
A and B always distinct.
A=(0,0) B=(10,0) P=(5,3) -> INSIDE
A=(0,0) B=(10,0) P=(-2,3) -> BEFORE
A=(0,0) B=(10,0) P=(12,3) -> AFTER
A=(0,0) B=(10,0) P=(0,5) -> INSIDE the foot is exactly A
This is the classification that decides which formula the point-to-segment
distance in #2316 uses, so it is worth getting right on its own before the
distance is asked for.
## What most people try first
Computing the foot. Parametrise the line as A + t * (B - A) and solve for t:
t = dot(B - A, P - A) / |AB|^2
then test 0 <= t <= 1. That is correct, and it is a DIVISION, so in floating
point the three answers near a boundary become a matter of rounding, and the
exact cases, the foot sitting precisely on A, come out as luck.
## Two dot products and no division at all
The denominator |AB|^2 is a squared length, so it is strictly positive
whenever A and B differ. Multiplying an inequality by a positive number
never flips it, so
t < 0 is exactly dot(B - A, P - A) < 0
t > 1 is exactly dot(A - B, P - B) < 0
The second line is the first one applied from the other end, which is worth noticing because it means one small function answers both. So:
if dot(B - A, P - A) < 0: BEFORE
elif dot(A - B, P - B) < 0: AFTER
else: INSIDE
## Why it is correct
dot(B - A, P - A) is positive exactly when the angle at A between the
segment direction and the direction to P is acute, which is exactly when P
lies on the B side of the line through A perpendicular to AB. The foot of
the perpendicular lies on that same side, so the sign of that dot product is
precisely the BEFORE test. The symmetric statement at B gives AFTER, and
if neither fires the foot is between the two perpendicular lines, which is the
segment. Nothing here is approximate: each test is the sign of an integer.
## The boundaries the statement settles
A dot product of exactly zero means the foot is exactly on an endpoint, and the
tests use a strict <, so zero falls through to INSIDE. That matches the
statement, and it is the case a careless <= gets wrong. P lying ON the
segment gives two non-negative dot products and so INSIDE, as it should.
A and B are guaranteed distinct, so the degenerate zero-length segment,
where every classification is defensible and none is forced, does not arise.
## Width
Coordinates satisfy |x|, |y| <= 10^6, so a difference reaches 2 * 10^6, a
product 4 * 10^12 and a dot product 8 * 10^12. That overflows a signed
32-bit integer, which stops at 2147483647, and a wrapped dot product flips its
SIGN, so the answer changes word rather than drifting. One declared test uses a
segment a million units long where a 32 bit build answers BEFORE for a point
past B. The value is below 2^53 = 9007199254740992, so a JavaScript Number
is exact and no bitwise operator may appear.
## Cost
O(1) per query, O(q) overall.
Constraints - `1 <= q <= 100000` - `-1000000 <= ax, ay, bx, by, px, py <= 1000000` - `A` and `B` are always distinct, so the segment has positive length - a foot landing exactly on `A` or on `B` is `INSIDE` - a dot product reaches `8 * 10^12`, so a 64-bit integer is needed
Input
The first line contains an integer q.
Each of the next q lines contains six integers ax ay bx by px py, giving A, B and P.
Output
For each query print one word on its own line: BEFORE, AFTER or INSIDE, in upper case.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.