Solution: Queries on Number of Points Inside a Circle

Statement

Given an array of points, where each point is represented as points[i]$\text = [x_i, y_i]$, which are the coordinates of the $i^{th}$ point on an X-Y plane where some points may have identical coordinates. Additionally, given an array of queries, where each queries[j] $\text = [x_j, y_j, r_j]$represents a circle centered at the point $[x_j, y_j]$ with a radius $r_j$.

For each query, your task is to determine how many points lie within or on the boundary of the specified circle. The function should return an array answer, where answer[j] holds the number of points inside the $j^{th}$ circle.

Note: Points on the circle’s edge should also be counted inside the circle.

Constraints:

• $1 \leq$ points.length $\leq 100$

• points[i].length $== 2$

• $0 \leq x_i, y_i$ $\leq 100$

• $1 \leq$ queries.length $\leq 100$

• queries[j].length $== 3$

• $0 \leq x_j, y_j$ $\leq 100$

• $1 \leq r_j$ $\leq 100$

Solution

To achieve this, the approach uses sorting and binary search to minimize the number of points examined for each query. Sorting the points based on their $x$-coordinates allows the solution to quickly narrow down the relevant points for each circle using binary search. Sorting ensures that points are processed in increasing order, optimizing finding ranges along the $x$-axis.

1. A point $(x,y)$ lies inside or on the boundary of a circle centered at $(x_j, y_j​)$ with radius $r_j$​ if the following condition holds:

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space(x−x_j​)^2+(y−y_j​)^2≤r_j^2$​

Note: The formula above compares the squared distance with the squared radius to avoid unnecessary square root computations.

2. By sorting the points by their x-coordinate, the algorithm narrows them down to those within the range $[x_j−r_j​,x_j​+r_j​]$ along the $x$-axis. This step significantly reduces the number of points that must be checked against the circle’s boundary, particularly when points are sparsely distributed.

3. To further optimize the search, binary search is applied on the sorted points to quickly locate the first point with an x-coordinate $\geq x_j - r_j$ and the last point with an x-coordinate $\leq x_j​ + r_j$​. This efficiently identifies the relevant subset of points that might fall inside the circle, reducing the search space from the entire set of points to only those within this range.

4. Once the $x$-coordinate range is identified, the algorithm iterates only over the subset of points within this range. For each point, the circle’s equation is used to verify if the point lies inside or on the circle’s boundary.

Here’s the step-by-step implementation of the solution:

1. Initialize an array, answer, to store the result for each query.

2. Sorts the points to allow range queries using binary search.

3. For every query (xj, yj, rj):

   1. Find the first point where x ≥ xj - rj using the binarySearch helper function with the parameter findLeft set to TRUE and store it to the left. This starts the range of relevant points.

   2. Find the first point where x > xj + rj using the binarySearch helper function with the parameter findLeft set to FALSE and store it to the right. This ends the range of relevant points.

   3. Together, points from left to right give the subset of points that could fall within the circle’s range.

   4. Iterate through points from left to right:

      1. Check if each point (x, y) satisfies the distance formula (xj - x)2 + (yj - y)2 ≤ rj2

         1. If TRUE, increment count by $1$. This ensures that only points inside or on the circle’s boundary are counted.

   5. Append the count to the answer.

4. After processing all queries, return the answer.

The helper function, binarySearch, with the findLeft parameter set to TRUE, uses binary search to find the smallest index in the sorted points array where the x-coordinate is greater than or equal to the lower bound of the circle’s range $(x_j​−r_j​)$. This ensures that only points that could fall inside the circle are considered in subsequent calculations. Similarly, the helper function binarySearch with the findLeft parameter set to FALSE uses binary search to find the smallest index where the x-coordinate is strictly greater than the upper bound of the circle’s range $(x_j+r_j​)$. This ensures that points beyond the circle’s range are excluded from further checks. By leveraging binary search, the algorithm efficiently determines the subset of points that need to be examined, significantly reducing the number of comparisons needed.

Let’s look at the following illustration to get a better understanding of the solution: