This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging

describe

You are given an array points where points[i] = [xi, yi] is the coordinates of the ith 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 jth circle. Points on the border of the circle are considered inside.

Return an array answer, where answer[j] is the answer to the jth query.

Example 1:

Input: points = [[1, 3], [3], [5], [2]], the queries = [,3,1 [2], [4,3,1], [1,1,2]] Output:,2,2 [3] Explanation: The points and circles are shown above. queries[0] is the green circle, queries[1] is the red circle, and queries[2] is the blue circle.Copy the code

Example 2:

Input: points = [[1, 1], [2], [3], [4], [5, 5]], the queries = [,2,2 [1], [2,2,2], 31 [4], [4 filling]] Output: Explanation:,3,2,4 [2] The points and circles are shown above. queries[0] is green, queries[1] is red, queries[2] is blue, and queries[3] is purple.Copy the code

Note:

  • 1 <= points.length <= 500
  • points[i].length == 2
  • 0 <= x​​​​​​i, y​​​​​​i <= 500
  • 1 <= queries.length <= 500
  • queries[j].length == 3
  • 0 <= xj, yj< = 500
  • 1 <= rj< = 500
  • All coordinates are integers.

Follow up: Could you find the answer for each query in better complexity than O(n)?

parsing

Each circle element has three values. The first two represent the center point as the position, and the third represents the radius of the circle. Calculate the number of points in each circle, and calculate the order in which the circle appears. Displays the number of points that each circle can contain in the list, with valid points if they happen to be on the edge. The idea is simple:

  • Initialize a result list with the number of circles in length
  • Add result[I] to the list of points and to the list of queries. Add result[I] to the list of points and to the list of queries. Add result[I] to the list of queries
  • When the traversal is complete, return result

answer

class Solution(object):
    def countPoints(self, points, queries):
        """
        :type points: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        result = [0] * len(queries)
        for point in points:
            x = point[0]
            y = point[1]
            for i,query in enumerate(queries):
                xx = query[0]
                yy = query[1]
                r = query[2]
                if abs(xx-x)**2+abs(yy-y)**2<=r**2:
                    result[i] += 1
        return result
        	      
		
Copy the code

The results

Runtime: 10000 ms, the linked list for Queries on Number of Points Inside a Circle. Submissions for Queries on Number of Points Inside a CircleCopy the code

thinking

Follow up: Could you find the answer for each query in better complexity than O(n)? This means that we need to reduce the time complexity to O(n), which is a bit difficult, it is equivalent to only one time to iterate the result, there is no idea for the moment.

Link: leetcode.com/problems/qu…

Your support is my greatest motivation