A forklift robot at point p wants to drive in a straight line to point q across a loading bay. The bay is full of crates, each an axis-aligned rectangle (x1, y1, x2, y2) with x1 < x2 and y1 < y2: it covers every point (x, y) with x1 <= x <= x2 and y1 <= y <= y2, its border included. Coordinates are whole centimetres, x to the right and y up.
A crate is in the way when the segment from p to q (both end points included) shares at least one point with it. Touching counts: running along a crate's side, or through one of its corners, is in the way too, because the forklift has no clearance to spare.
Write crates_in_way(p, q, crates) that returns the sorted list of the indices of the crates in the way (an empty list when the straight drive is clear). When p == q the segment is the single point p.
Examples
Input: p = (0, 0), q = (10, 10),
crates = [(2, 6, 4, 9), (4, 4, 6, 5), (8, 0, 9, 2), (10, 10, 12, 12)]
Output: [1, 3]
Explanation: the drive along y = x crosses crate 1 from (4, 4) to (5, 5),
and ends on the corner (10, 10) of crate 3. Crates 0 and 2 are clear.
Input: p = (0, 0), q = (10, 0), crates = [(3, 0, 5, 2), (6, -3, 7, -1), (11, -1, 12, 1)]
Output: [0]
Explanation: the drive runs along the bottom side of crate 0. Crate 2 lies on the
same line, but beyond q.
Input: p = (5, 5), q = (5, 5), crates = [(0, 0, 4, 4), (5, 5, 6, 6)]
Output: [1]
Constraints
- the answer must be exact: use whole-number arithmetic, not floats
Goals
- Decide exactly, with whole numbers, whether a segment meets a closed rectangle
- Treat touching an edge or a corner as a hit
- Handle the segment inside a rectangle and the segment of length zero