Queries on Number of Points Inside a Circle
You are given an array points where points[i] = [xi, yi] is the coordinates of the i^th point on a 2D plane. Multiple points can have the same coordinates.
You are also given an array queries where queries[j] = [xj, yj, rj] describes a circle centered at (xj, yj) with a radius of rj.
For each query queries[j], compute the number of points inside the j^th circle. Points on the border of the circle are considered inside.
Return an array answer, where answer[j] is the answer to the j^th query.
Follow up: Could you find the answer for each query in better complexity than O(n)?
Example 1
Input
points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]Output
[3,2,2]The green, red, and blue circles contain 3, 2, and 2 points respectively.
Example 2
Input
points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]Output
[2,3,2,4]The green, red, blue, and purple circles contain 2, 3, 2, and 4 points respectively.
Constraints
- 1 <= points.length <= 500
- points[i].length == 2
- 0 <= xi, yi <= 500
- 1 <= queries.length <= 500
- queries[j].length == 3
- 0 <= xj, yj <= 500
- 1 <= rj <= 500
- All coordinates are integers.