A directed line passes through p1 and then p2 (standing at p1, looking toward p2). Write point_location(p1, p2, p3) -> str returning
"LEFT"ifp3is to the left of that line,"RIGHT"if it's to the right,"TOUCH"if it lies exactly on the (infinite) line.
Points are (x, y) tuples of integers, and p1 != p2.
Stay in integers: slopes or angles in floating point give wrong answers when the point is a tiny distance from a long line.
point_location((1, 1), (5, 3), (2, 3)) # "LEFT"
point_location((1, 1), (5, 3), (2, 1)) # "RIGHT"
point_location((1, 1), (5, 3), (3, 2)) # "TOUCH"
point_location((0, 0), (0, 4), (-1, 9)) # "LEFT" (line pointing straight up)
Constraints: every coordinate is between -10^9 and 10^9.
Show hint
Look at the sign of the cross product of p2 - p1 and p3 - p1, that is (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1).