Problem Description
You are given an array points where points[i] = [xi, yi] is the coordinates of the ith point on a 2D plane. 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 jth circle, including points on the border. Return an array answer, where answer[j] is the answer to the jth query.
Key Insights
- Each query defines a circle in a 2D plane.
- A point is considered inside or on the border of the circle if the distance from the point to the circle's center is less than or equal to the radius.
- The distance between a point (xi, yi) and circle center (xj, yj) can be calculated using the formula: (xi - xj)² + (yi - yj)² ≤ rj².
- The problem requires counting points for multiple queries, which could be optimized.
Space and Time Complexity
Time Complexity: O(m * n), where m is the number of queries and n is the number of points.
Space Complexity: O(1), as we only use a constant amount of additional space for counting.
Solution
To solve the problem, we can iterate through each query and for each query, check all points to see if they fall within the defined circle. We utilize the distance formula to determine if a point is inside or on the border of the circle. This straightforward approach results in a time complexity of O(m * n).