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

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

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

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

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.