Locate Cars with a Boolean Square-Scan API

Problem Statement

You are tasked with locating all autonomous vehicles operating within an N x N tracking area. You do not have direct access to vehicle coordinates; instead, you interact with an external sensor system via a Boolean square scanner API.

The tracking area spans coordinates (r, c) where 0 <= r < N and 0 <= c < N, and N is guaranteed to be a power of 2 (N = 2^k). Vehicles occupy discrete integer coordinates (r, c).

The Scanner interface provides a single method:

• scanner.has_vehicle(r: int, c: int, size: int) -> bool: Returns True if at least one vehicle exists inside the axis-aligned square with top-left corner at (r, c) spanning to (r + size - 1, c + size - 1), inclusive. It returns False otherwise.

Implement the function locate_vehicles(n: int, scanner: Scanner) -> list[tuple[int, int]] that returns a list of all vehicle coordinates in the grid. Each coordinate should be returned as a tuple (r, c). The returned list may be in any order.

Optimize your solution to minimize the total number of calls to scanner.has_vehicle.

Interface

class Scanner:
    def has_vehicle(self, r: int, c: int, size: int) -> bool:
        pass

def locate_vehicles(n: int, scanner: Scanner) -> list[tuple[int, int]]:
    pass

Constraints

• N = 2^k where 0 <= k <= 10 (i.e., 1 <= N <= 1024).
• The total number of vehicles V satisfies 0 <= V <= min(100, N * N).
• Each cell (r, c) contains at most one vehicle.
• r, c, and size passed to has_vehicle must satisfy 0 <= r, c <= N - size and 1 <= size <= N.

Examples

Example 1

Input: N = 4, Vehicles at [(1, 2), (3, 3)]
Output: [(1, 2), (3, 3)]
Explanation:
- A scan across the whole 4x4 area returns True.
- Dividing into four 2x2 quadrants:
  - Top-left [0..1, 0..1]: False
  - Top-right [0..1, 2..3]: True -> subdivided into 1x1 cells, finds (1, 2)
  - Bottom-left [2..3, 0..1]: False
  - Bottom-right [2..3, 2..3]: True -> subdivided into 1x1 cells, finds (3, 3)
Total calls are significantly fewer than scanning all 16 cells individually.

Example 2

Input: N = 2, Vehicles at []
Output: []
Explanation:
`scanner.has_vehicle(0, 0, 2)` returns False immediately. No further queries are needed.

Edge Cases

• Empty grid (V = 0): Should exit after a single query at size N.
• Full grid or single cell grid (N = 1).
• Multiple vehicles located in the same quadrant or row.