Radar Overlaps and Undetected Crossing of a Rectangular Room

Radars are installed inside a rectangular room bounded by four walls: the left wall `x = 0`, the right wall `x = width`, the bottom wall `y = 0` and the top wall `y = height`. Radar `i` sits at the integer point `(x_i, y_i)` inside the room and detects everything within distance `r_i` of that point, the boundary included. The interview asked two questions about this setup, and your function answers both: 1. For every radar, which other radars overlap it? 2. Can an object travel from the left wall to the right wall without ever being detected? ### Function Signature ```python def analyze_radars(width: int, height: int, radars: list[list[int]]) -> tuple[list[list[int]], bool]: ``` `radars[i] = [x_i, y_i, r_i]`. Return the pair `(overlaps, can_cross)`. ### Rules - The coverage of radar `i` is the closed disk of points `(x, y)` with `(x - x_i)^2 + (y - y_i)^2 <= r_i^2`. - Radars `i` and `j` (with `i != j`) overlap when their coverage disks share at least one point, that is, when `(x_i - x_j)^2 + (y_i - y_j)^2 <= (r_i + r_j)^2`. Disks that touch at a single point overlap. - `overlaps` has one list per radar, in input order. `overlaps[i]` contains every index `j` of a radar that overlaps radar `i`, in increasing order, and is empty if there is none. - The object is a point. It may start at any point of the left wall (`x = 0`, `0 <= y <= height`), follow any continuous path that stays inside the closed rectangle (the walls included), and end at any point of the right wall (`x = width`). It is detected if any point of its path, including the start and end points, lies in the coverage of some radar. - `can_cross` is `True` if at least one path avoids the coverage of every radar, and `False` otherwise. - Coverage may extend beyond the walls; only the part inside the room affects the object. - With no radars, the result is `([], True)`. ### Constraints - `1 <= width <= 10^6` and `1 <= height <= 10^6`. - `0 <= len(radars) <= 1000`. - For every radar: `0 <= x_i <= width`, `0 <= y_i <= height`, and `1 <= r_i <= 10^6`. All values are integers. - Several radars may share a center, or even be identical; identical radars overlap each other. - Squared distances and squared radius sums reach about `4 * 10^12`, beyond `2^31 - 1`, so use 64-bit integer arithmetic. All values stay well within `2^53`. ### Examples **Example 1** ```text Input: width = 10, height = 6, radars = [[2, 1, 2], [4, 3, 2], [5, 5, 1], [9, 1, 1]] Output: ([[1], [0, 2], [1], []], False) ``` Radars 0 and 1 overlap (squared distance `8 <= 16`), and radars 1 and 2 overlap (`5 <= 9`); no other pair does. Radar 0 reaches below the bottom wall, radar 2 touches the top wall at `(5, 6)`, and together radars 0, 1 and 2 cover an unbroken band from the bottom wall to the top wall, so the object cannot get past them. **Example 2** ```text Input: width = 8, height = 6, radars = [[2, 1, 1], [3, 2, 1], [6, 5, 2]] Output: ([[1], [0], []], True) ``` Radars 0 and 1 overlap (`2 <= 4`). Radar 2 overlaps neither radar 1 (`18 > 9`) nor radar 0 (`32 > 9`). The straight segments `(0, 3.5) -> (4, 3.5) -> (5, 1) -> (8, 1)` stay outside every radar's coverage. **Example 3** ```text Input: width = 10, height = 6, radars = [[2, 2, 2], [6, 2, 2], [6, 5, 1]] Output: ([[1], [0, 2], [1]], False) ``` Radars 0 and 1 touch at `(4, 2)` (`16 <= 16`) and radars 1 and 2 touch at `(6, 4)` (`9 <= 9`). Radar 0 touches the bottom wall at `(2, 0)` and radar 2 touches the top wall at `(6, 6)`. Touching points are detected, so there is no gap the object could slip through.