Show problems as
Classic problem #1828MediumArrayMathGeometry

Queries on Number of Points Inside a Circle

Real-world version: Sensors Within Each Scan Radius
Tracked in this browser only
Read Queries on Number of Points Inside a Circle on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey grid carries fixed sensors. sensors[i] = [x, y] gives the integer coordinates of sensor i; two sensors may share a position.

A radar makes a series of circular sweeps. scans[j] = [x, y, r] describes a sweep centred at (x, y) with radius r. A sensor is covered by that sweep when its straight-line distance to the centre is at most r. A sensor lying exactly on the circle of radius r counts as covered.

Go through the sweeps in the order listed, work out how many sensors each one covers, and give back those totals as a single list. Two sensors on the same position are tallied separately.

Examples

Example 1

Input
sensors = [[7, 2], [2, 9], [10, 10], [6, 6]], scans = [[6, 3, 2], [9, 9, 3], [0, 0, 4]]
Output
[1, 1, 0]

The first sweep reaches sensor (7, 2), which sits a distance of about 1.41 from (6, 3). The second reaches sensor (10, 10), about 1.41 from (9, 9). The third covers no sensor at all, since the nearest is (6, 6) at about 8.49 from the origin.

Example 2

Input
sensors = [[3, 4], [0, 5], [4, 4]], scans = [[0, 0, 5]]
Output
[2]

Sensors (3, 4) and (0, 5) are both exactly 5 from the centre, so both count as covered. Sensor (4, 4) is about 5.66 away and is not.

Example 3

Input
sensors = [[2, 2], [2, 2], [7, 7]], scans = [[2, 2, 1], [7, 7, 9]]
Output
[2, 3]

The first sweep is centred on the position two sensors share, so it covers both of them. The second sweep has a radius of 9 and reaches all three sensors.

Constraints

  • 1 <= sensors.length <= 500
  • sensors[i].length == 2
  • 0 <= sensors[i][j] <= 500
  • 1 <= scans.length <= 500
  • scans[j].length == 3
  • 0 <= scans[i][j] <= 500
  • Sweep j is [x_j, y_j, r_j] with 1 <= r_j <= 500.
  • All coordinates and radii are integers.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def sensors_in_range(sensors: list[list[int]], scans: list[list[int]]) -> list[int]:
Java
public int[] sensorsInRange(int[][] sensors, int[][] scans)

More on the same topics