统计一个圆中点的数目

标签: 几何 数组 数学

难度: Medium

给你一个数组 points ，其中 points[i] = [xi, yi] ，表示第 i 个点在二维平面上的坐标。多个点可能会有 相同 的坐标。

同时给你一个数组 queries ，其中 queries[j] = [xj, yj, rj] ，表示一个圆心在 (xj, yj) 且半径为 rj 的圆。

对于每一个查询 queries[j] ，计算在第 j 个圆 内 点的数目。如果一个点在圆的 边界上 ，我们同样认为它在圆 内 。

请你返回一个数组 answer ，其中 answer[j]是第 j 个查询的答案。

 

示例 1：

输入：points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
输出：[3,2,2]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆。

示例 2：

输入：points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
输出：[2,3,2,4]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆，queries[3] 是紫色的圆。

 

提示：

  • 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
  • 所有的坐标都是整数。

Submission

运行时间: 376 ms

内存: 16.3 MB

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        l = len(queries)
        res = [0] * l
        def inside(x0, y0, r):
            res = 0
            for x, y in points:
                if (x-x0)**2 + (y-y0)**2 <= r*r:
                    res += 1
            return res
        
        for i, (x0, y0, r) in enumerate(queries):
            res[i] = inside(x0, y0, r)

        return res

Explain

该题解采用了直接遍历的方法来解决问题。对于每个查询圆，通过一个辅助函数 `inside` 来判断每个点是否位于该查询圆内。具体而言，对于每个查询圆心 `(x0, y0)` 和半径 `r`，函数 `inside` 会遍历所有点 `(x, y)`，计算点到圆心的距离的平方 `(x-x0)^2 + (y-y0)^2`，并检查该值是否小于等于半径的平方 `r^2`。如果是，说明点在圆内或圆边上，累计计数。最后，将每个查询的结果存入结果数组 `res` 中。

时间复杂度: O(p * q)

空间复杂度: O(q)

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        l = len(queries)
        res = [0] * l  # 结果数组，用于存储每个查询的结果
        def inside(x0, y0, r):
            res = 0  # 用于计数当前圆内的点数
            for x, y in points:  # 遍历所有点
                if (x-x0)**2 + (y-y0)**2 <= r*r:  # 计算点到圆心的距离的平方，并与半径的平方比较
                    res += 1  # 如果点在圆内（包括边界），计数器加一
            return res  # 返回圆内点的总数
        
        for i, (x0, y0, r) in enumerate(queries):  # 遍历所有查询
            res[i] = inside(x0, y0, r)  # 调用inside函数计算每个圆内的点数，并存入结果数组

        return res  # 返回最终结果列表

Explore

使用点到圆心的距离平方来比较是为了避免计算平方根，这样可以减少计算复杂度和计算误差。开平方根是一个相对耗时的操作，并且可能引入浮点数的不精确性。通过比较距离的平方与半径平方，可以有效地提高算法的效率和结果的准确性。

是否将圆边界上的点计算在内通常取决于题目的具体要求。在大多数情况下，计算几何问题默认包括边界上的点，因为这符合几何直觉。但是，不同的题目可能会有不同的规定，因此在解决具体问题时，需要仔细阅读题目说明来判断。

该题解采用了简单直接的方法，没有考虑点的分布情况。在点的分布极为稀疏或集中的情况下，这种方法可能不是最高效的。例如，如果大部分点都集中在某个区域，而查询的圆离这些点很远，遍历所有点的做法会造成不必要的计算。在这种情况下，可以考虑使用空间分割或数据索引方法（如四叉树、k-d树等），以提高查询效率。

当点的坐标或圆的参数非常大时，确实需要考虑整数溢出的问题。在计算点到圆心的距离平方时，坐标值差的平方可能超出常规整数类型的范围。在编程实践中，可以通过使用更大范围的整数类型（如Python中的长整型），或者在必要时进行适当的范围检查和数据归一化，来避免这种溢出问题。