1828-统计一个圆中点的数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

给你一个数组 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
  • 所有的坐标都是整数。

方法一：枚举每个点是否在每个圆中

思路与算法

我们可以使用二重循环，对于每一个查询，枚举所有的点，依次判断它们是否在查询的圆中即可。

如果查询圆的圆心为 (c_x, c_y)，半径为 c_r，枚举的点坐标为 (p_x, p_y)，那么点在圆中（包括在圆上的情况）当且仅当点到圆心的距离小于等于半径。我们可以用以下方法进行判断：

(c_x-p_x)^2 + (c_y-p_y)^2 \leq c_r^2

注意这里两侧的距离都进行了平方操作，这样可以避免引入浮点数，产生不必要的误差。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
        int m = points.size(), n = queries.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            int cx = queries[i][0], cy = queries[i][1], cr = queries[i][2];
            for (int j = 0; j < m; ++j) {
                int px = points[j][0], py = points[j][1];
                if ((cx - px) * (cx - px) + (cy - py) * (cy - py) <= cr * cr) {
                    ++ans[i];
                }
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] countPoints(int[][] points, int[][] queries) {
        int m = points.length, n = queries.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int cx = queries[i][0], cy = queries[i][1], cr = queries[i][2];
            for (int j = 0; j < m; ++j) {
                int px = points[j][0], py = points[j][1];
                if ((cx - px) * (cx - px) + (cy - py) * (cy - py) <= cr * cr) {
                    ++ans[i];
                }
            }
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int[] CountPoints(int[][] points, int[][] queries) {
        int m = points.Length, n = queries.Length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int cx = queries[i][0], cy = queries[i][1], cr = queries[i][2];
            for (int j = 0; j < m; ++j) {
                int px = points[j][0], py = points[j][1];
                if ((cx - px) * (cx - px) + (cy - py) * (cy - py) <= cr * cr) {
                    ++ans[i];
                }
            }
        }
        return ans;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        ans = [0] * len(queries)

        for i, (cx, cy, cr) in enumerate(queries):
            for (px, py) in points:
                if (cx - px) ** 2 + (cy - py) ** 2 <= cr ** 2:
                    ans[i] += 1
        
        return ans
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int* countPoints(int** points, int pointsSize, int* pointsColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {    
    int *ans = (int *)malloc(sizeof(int) * queriesSize);
    memset(ans, 0, sizeof(int) * queriesSize);
    for (int i = 0; i < queriesSize; ++i) {
        int cx = queries[i][0], cy = queries[i][1], cr = queries[i][2];
        for (int j = 0; j < pointsSize; ++j) {
            int px = points[j][0], py = points[j][1];
            if ((cx - px) * (cx - px) + (cy - py) * (cy - py) <= cr * cr) {
                ++ans[i];
            }
        }
    }
    *returnSize = queriesSize;
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var countPoints = function(points, queries) {
    const m = points.length, n = queries.length;
    const ans = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        let cx = queries[i][0], cy = queries[i][1], cr = queries[i][2];
        for (let j = 0; j < m; ++j) {
            let px = points[j][0], py = points[j][1];
            if ((cx - px) * (cx - px) + (cy - py) * (cy - py) <= cr * cr) {
                ++ans[i];
            }
        }
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
func countPoints(points [][]int, queries [][]int) []int {
    ans := make([]int, len(queries))
    for i, q := range queries {
        x, y, r := q[0], q[1], q[2]
        for _, p := range points {
            if (p[0]-x)*(p[0]-x)+(p[1]-y)*(p[1]-y) <= r*r {
                ans[i]++
            }
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：O(mn)，其中 m 和 n 分别是数组 points 和 queries 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
1828-统计一个圆中点的数目