Queries on Number of Points Inside a Circle
For each query, count points within radius — brute force with squared distance is fast enough.
3 min read
geometry brute-force
Problem#
For each query (qx, qy, r), count how many of the given points lie within (and including the boundary of) the circle centered at (qx, qy) with radius r.
Examples#
points=[[1,3],[3,3],[5,3],[2,2]],queries=[[2,3,1],[4,3,1],[1,1,2]]→[3,2,2].
Constraints#
1 <= points.length, queries.length <= 500, coords in[0, 500],1 <= r <= 500.
Approach#
Brute force: for each query, scan all points and check (dx*dx + dy*dy) <= r*r. n * q = 250000 ops — well within budget.
Solution#
class Solution {public: vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) { vector<int> ans; ans.reserve(queries.size()); for (auto& q : queries) { int qx = q[0], qy = q[1], r2 = q[2] * q[2], cnt = 0; for (auto& p : points) { int dx = p[0] - qx, dy = p[1] - qy; if (dx*dx + dy*dy <= r2) ++cnt; } ans.push_back(cnt); } return ans; }};func countPoints(points [][]int, queries [][]int) []int { ans := make([]int, 0, len(queries)) for _, q := range queries { qx, qy, r2 := q[0], q[1], q[2]*q[2] cnt := 0 for _, p := range points { dx, dy := p[0]-qx, p[1]-qy if dx*dx+dy*dy <= r2 { cnt++ } } ans = append(ans, cnt) } return ans}from typing import List
class Solution: def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]: ans: List[int] = [] for qx, qy, r in queries: r2 = r * r cnt = 0 for px, py in points: dx, dy = px - qx, py - qy if dx * dx + dy * dy <= r2: cnt += 1 ans.append(cnt) return ansfunction countPoints(points, queries) { const ans = []; for (const [qx, qy, r] of queries) { const r2 = r * r; let cnt = 0; for (const [px, py] of points) { const dx = px - qx, dy = py - qy; if (dx * dx + dy * dy <= r2) cnt++; } ans.push(cnt); } return ans;}class Solution { public int[] countPoints(int[][] points, int[][] queries) { int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int qx = queries[i][0], qy = queries[i][1]; int r2 = queries[i][2] * queries[i][2]; int cnt = 0; for (int[] p : points) { int dx = p[0] - qx, dy = p[1] - qy; if (dx * dx + dy * dy <= r2) cnt++; } ans[i] = cnt; } return ans; }}function countPoints(points: number[][], queries: number[][]): number[] { const ans: number[] = []; for (const [qx, qy, r] of queries) { const r2 = r * r; let cnt = 0; for (const [px, py] of points) { const dx = px - qx, dy = py - qy; if (dx * dx + dy * dy <= r2) cnt++; } ans.push(cnt); } return ans;}Editorial#
Squared distances dodge floating point entirely. With both n, q <= 500, brute force is the right call — any preprocessing structure (k-d tree, range tree) costs more than the savings.
Complexity#
- Time:
O(n * q). - Space:
O(q).
Concept revision#
Related#