A greenhouse has several rovers. Each has a pose (x, y, theta): a position on the greenhouse's metre grid (x to the right, y up; whole numbers) and a heading in radians, counter-clockwise from the +x axis. A plant at the position goal = (gx, gy) (whole numbers) needs water, and the dispatcher sends one rover, chosen like this:
- the rover closest to the goal (straight-line distance) is sent;
- among rovers equally close, the one that must turn least to face the goal: the size of the shorter turn from its heading to the direction of the goal, a number from 0 to \pi. A rover already standing on the goal needs no turn. Turns that differ by less than
1e-9count as equal; - if there is still a tie, the rover that comes first in the list.
Write send_rover(rovers, goal) that returns the index of the rover sent.
Examples
Input: rovers = [(0, 0, 1.5707963267948966), (4, 0, 3.141592653589793), (2, 3, 0)], goal = (2, 0)
Output: 1
Explanation: rovers 0 and 1 are both 2 m away. Rover 0 faces up and would turn pi/2;
rover 1 already faces the goal.
Input: rovers = [(1, 5, -1.0), (5, 1, 2.0), (-3, 3, 0)], goal = (1, 1)
Output: 0
Explanation: rovers 0 and 1 are both 4 m away. Rover 0 must turn 0.5708 to face straight
down; rover 1 must turn 1.1416 to face the -x direction.
Input: rovers = [(0, 0, 0), (3, 4, 2.0)], goal = (3, 4)
Output: 1
Explanation: rover 1 is already on the goal.
Goals
- Rank robots by distance to a goal, then by how far each must turn to face it
- Compare distances exactly by comparing squared distances of whole-number positions
- Apply a chain of tie-breaks in a single pass