A robot tractor ploughs a straight furrow: it drives from the waypoint a towards the waypoint b and keeps going along that line. Before it starts, the farmer has marked stakes in the field, and the tractor must know which side of its line of travel each stake is on, as seen by the driver facing from a towards b:
"left"if the stake is on the driver's left of the line,"right"if it is on the driver's right,"on"if it lies exactly on the line, anywhere along it: betweenaandb, beyondb, or behinda(the line extends both ways).
Coordinates are whole metres in the world frame (x to the right, y up). Write stake_sides(a, b, stakes) that returns the list of labels, one per stake, in order.
Examples
Input: a = (0, 0), b = (4, 0), stakes = [(2, 3), (1, -1), (6, 0), (-3, 0)]
Output: ["left", "right", "on", "on"]
Explanation: driving east, north is on the left. (6, 0) is ahead on the line, (-3, 0) behind it.
Input: a = (1, 1), b = (3, 5), stakes = [(2, 3), (0, 5), (5, 1)]
Output: ["on", "left", "right"]
Constraints
a != b
Goals
- Use the sign of a 2D cross product to tell left from right
- Treat points behind the start or past the end as on the line when they are collinear
- Keep the test exact by staying with whole numbers