2271. Which Way Does the Turn Go
Three points A, B and C are given. Walking from A to B and then on to
C, print LEFT if the second step turns left, RIGHT if it turns right, and
STRAIGHT if the three points lie on one line. Answer q such triples.
(0,0) (1,0) (1,1) -> LEFT
(0,0) (1,0) (1,-1) -> RIGHT
(0,0) (1,0) (2,0) -> STRAIGHT
## What most people try first
Slopes. Compare the slope of AB with the slope of AC, and decide from
which is larger. Two things go wrong, and both are fatal rather than annoying.
A vertical segment has no slope, so dx = 0 needs a special case, and so does
the combination of one vertical and one not. Every slope-based solution grows a
small thicket of these.
Worse, a slope is a DIVISION, so comparing two slopes in floating point compares
two rounded numbers. For (0,0) (3,1) (6,2), which really is straight, the two
slopes are both one third, and one third is not representable in binary. Whether
the two roundings come out equal depends on the exact values, so the answer
becomes a matter of luck. An exact question deserves an exact method.
## The cross product, and why it answers this
Take the two step vectors and form
cross = (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
Its SIGN is the answer: positive means left, negative means right, zero means collinear.
This is exactly the slope comparison with the division cleared away. "Slope of
AC greater than slope of AB" is
(Cy - Ay) / (Cx - Ax) > (By - Ay) / (Bx - Ax)
and multiplying out by both denominators gives the cross product, with the usual caveat that multiplying an inequality by a negative number flips it. The cross product formulation has no such caveat, because it is a statement about a determinant rather than about a quotient: the sign of the determinant is the orientation, full stop.
Three things to notice. It is an integer whenever the coordinates are, so the comparison with zero is exact. It needs no special case for vertical segments, since nothing is divided. And it is zero exactly when the points are collinear, including when two of them coincide, which is the case a slope comparison cannot see at all.
## Everything in this topic rests on this
Segment intersection is four of these tests. Polygon area is a sum of them.
Point in polygon counts them. The convex hull keeps a point exactly when one of
them has the right sign. So it is worth being certain of the sign convention
before going further: with y increasing upward, a positive cross product is an
ANTICLOCKWISE turn, which this problem calls LEFT.
## Width
Coordinates satisfy |x|, |y| <= 10^6, so each difference is at most
2 * 10^6, each product at most 4 * 10^12, and the cross product at most
8 * 10^12 in magnitude. That requires a 64-bit integer: a signed 32-bit one
holds only 2147483647, so a 32-bit cross product wraps and reports the wrong
TURN, not merely a wrong number.
In JavaScript the value is below 2^53 = 9007199254740992, so a plain Number
holds it exactly and no BigInt is needed. Note that the arithmetic must be
ordinary multiplication and subtraction: the bitwise operators would coerce to
32 bits and must not appear.
Constraints - `1 ≤ q ≤ 100000` - `-1000000 ≤ ax, ay, bx, by, cx, cy ≤ 1000000` - the three points need not be distinct
Input
The first line contains an integer q.
Each of the next q lines contains six integers ax ay bx by cx cy, the coordinates of A, B and C in that order, separated by spaces.
Output
For each triple print one word on its own line: LEFT, RIGHT or STRAIGHT, 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.