What is the core pattern in Queries on Number of Points Inside a Circle?

The problem relies on the array plus math pattern: iterating points and using Euclidean distance to count points inside each circle.

Do points on the circle edge count as inside?

Yes, any point with a distance equal to or less than the radius is considered inside the circle.

Can I optimize by pre-sorting points?

Sorting may help if you use spatial filtering or bounding box checks, but basic iteration suffices within the problem constraints.

Why use squared distances instead of actual distance?

Squared distances avoid floating point errors and unnecessary square root calculations, ensuring accurate counts for points on borders.

What is the expected output format?

Return an array of integers, where each element represents the number of points inside the corresponding circle query.

#1828

Medium

auto_awesome数组·数学

LeetCode 题解工作台

统计一个圆中点的数目

给你一个数组 points ，其中 points[i] = [x i , y i ] ，表示第 i 个点在二维平面上的坐标。多个点可能会有相同的坐标。同时给你一个数组 queries ，其中 queries[j] = [x j , y j , r j ] ，表示一个圆心在 (x j , y j…

数组数学几何

题目描述

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

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

对于每一个查询 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 <= x_j, y_j <= 500
1 <= r_j <= 500
所有的坐标都是整数。

lightbulb

解题思路

方法一：枚举

枚举所有的圆点 $(x, y, r)$ ，对于每个圆点，计算在圆内的点的个数，即可得到答案。

时间复杂度 $O(m \times n)$ ，其中 $m$ 和 $n$ 分别为数组 queries 的长度和 points 的长度。忽略答案的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countPoints(
        self, points: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        ans = []
        for x, y, r in queries:
            cnt = 0
            for i, j in points:
                dx, dy = i - x, j - y
                cnt += dx * dx + dy * dy <= r * r
            ans.append(cnt)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n * m), where n is the number of points and m is the number of queries, because each point may be checked against every circle. Space complexity is O(m) for the result array, with no additional significant memory usage.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you handling points exactly on the circle boundary correctly?
question_mark
Can you optimize distance computations to avoid square root operations?
question_mark
How would this approach scale if the number of points or queries increased?

warning

常见陷阱

外企场景

error
Using floating point square roots can miscount points on the border.
error
Forgetting to include points exactly at the circle's radius in the count.
error
Assuming all points are unique and skipping duplicates incorrectly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Counting points inside rectangles instead of circles using array iteration.
arrow_right_alt
Finding the closest point to each circle center instead of counting all points.
arrow_right_alt
Handling 3D points and spherical queries with the same distance check logic.

help

常见问题

外企场景

继续练习

#1610 可见点的最大数目 #2101 引爆最多的炸弹 #1515 服务中心的最佳位置