Given a list of 2D points on the X-Y plane, and a set of queries where each query represents a circle (with a center and a radius), your task is to determine, for each query, how many points from the list lie inside or on the boundary of the circle.
points where each element is a pair [x, y] representing a point's coordinates.queries array contains elements of the form [x_center, y_center, radius] representing the center and radius of a circle.
The core of the problem is checking whether each point lies within a given circle for every query. The naive approach is to check every point against every query, which is simple but potentially inefficient for large inputs. We recognize that the mathematical way to check if a point (x, y) is inside a circle centered at (x_c, y_c) with radius r is to verify if the squared distance (x - x_c)^2 + (y - y_c)^2 is less than or equal to r^2.
Initially, one might consider optimizing by preprocessing or using spatial data structures, but given the constraints of the problem (modest input sizes in LeetCode), a direct approach is both correct and efficient enough. The main idea is to loop through each query and, for each, check every point.
queries list.
(x_c, y_c) and the radius r.
points, calculate the squared distance to the query's center: dx = x - x_c, dy = y - y_c, and distance_squared = dx * dx + dy * dy.
distance_squared is less than or equal to r * r, the point is inside or on the circle. Increment a counter.
This approach is straightforward and leverages the mathematical definition of a circle. No advanced data structures are needed due to manageable input sizes.
Sample Input:
points = [[1,3],[3,3],[5,3],[2,2]]queries = [[2,3,1],[4,3,1],[1,1,2]]Processing Query 1: [2,3,1] (center: (2,3), radius: 1)
Count: 3
Processing Query 2: [4,3,1] (center: (4,3), radius: 1)
Count: 2
Processing Query 3: [1,1,2] (center: (1,1), radius: 2)
Count: 2
Final Output: [3, 2, 2]
Q queries and N points, the time complexity is O(Q * N).O(1) extra (excluding the output), as we only use counters and the output array.This problem is a classic application of coordinate geometry and brute-force checking. By leveraging the mathematical definition of a circle, we can efficiently determine if each point is within a given radius for each query. The straightforward approach is optimal given the problem constraints, and the solution demonstrates how simple math and iteration can solve real-world geometric queries effectively.
class Solution:
def countPoints(self, points, queries):
result = []
for x_c, y_c, r in queries:
count = 0
r2 = r * r
for x, y in points:
dx = x - x_c
dy = y - y_c
if dx * dx + dy * dy <= r2:
count += 1
result.append(count)
return result
class Solution {
public:
vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
vector<int> result;
for (const auto& q : queries) {
int x_c = q[0], y_c = q[1], r = q[2];
int r2 = r * r;
int count = 0;
for (const auto& p : points) {
int dx = p[0] - x_c;
int dy = p[1] - y_c;
if (dx * dx + dy * dy <= r2) {
count++;
}
}
result.push_back(count);
}
return result;
}
};
class Solution {
public int[] countPoints(int[][] points, int[][] queries) {
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int x_c = queries[i][0], y_c = queries[i][1], r = queries[i][2];
int r2 = r * r;
int count = 0;
for (int[] p : points) {
int dx = p[0] - x_c;
int dy = p[1] - y_c;
if (dx * dx + dy * dy <= r2) {
count++;
}
}
result[i] = count;
}
return result;
}
}
var countPoints = function(points, queries) {
let result = [];
for (let [x_c, y_c, r] of queries) {
let count = 0;
let r2 = r * r;
for (let [x, y] of points) {
let dx = x - x_c;
let dy = y - y_c;
if (dx * dx + dy * dy <= r2) {
count++;
}
}
result.push(count);
}
return result;
};