非常感謝你閱讀本文~
歡迎【👍點贊】【?收藏】【📝評論】~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子 https://le-yi.blog.csdn.net/ 博客原創~

1828. 統計一個圓中點的數目：

給你一個陣列 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 <= x_j, y_j <= 500
• 1 <= r_j <= 500
• 所有的坐標都是整數，

分析

• 二當家的剛看到題目先是有點懈怠心里，因為幾何知識都忘記了，感徑訓很復雜，
• 但是讀了題，仔細思考后發現點是否會落在圓內，就是要看點到圓心的距離是否小于等于圓的半徑，
• 假設圓心p₁的坐標是（x₁，y₁），點p₂的坐標是（x₂，y₂），那么點到圓心的距離就是 ( x 2 ? x 1 ) 2 + ( y 2 ? y 1 ) 2 \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} (x2??x1?)2+(y2??y1?)2 ?，
• 由于我們只需要比較距離和半徑哪個大，并不需要真的算出距離，所以可以距離不開方，而把半徑做平方，因為平方運算要比開方快，

題解

java

class Solution {
    public int[] countPoints(int[][] points, int[][] queries) {
        final int n   = queries.length;
        int[]     ans = new int[n];

        for (int i = 0; i < n; ++i) {
            int x = queries[i][0];
            int y = queries[i][1];
            int r = queries[i][2];
            int r2 = r * r;
            int maxX = x + r;
            int minX = x - r;
            int maxY = y + r;
            int minY = y - r;

            for (int[] p : points) {
                int px = p[0];
                int py = p[1];
                // 加速的判斷，是否有意義不好說，對于不符合的點會更快，對于符合的點會更慢，也許就互相抵消了
                if (px < minX || px > maxX
                    || py < minY || py > maxY) {
                    continue;
                }
                // 到圓心距離小于等于半徑的點就是滿足題目要求的點
                double dis = Math.pow(px - x, 2) + Math.pow(py - y, 2);
                if (dis <= r2) {
                    ans[i]++;
                }
            }
        }

        return ans;
    }
}

c

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countPoints(int** points, int pointsSize, int* pointsColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
    *returnSize = queriesSize;
    int *ans = malloc(sizeof(int) * queriesSize);

    for (int i = 0; i < queriesSize; ++i) {
        int x = queries[i][0];
        int y = queries[i][1];
        int r = queries[i][2];
        int r2 = r * r;
        int maxX = x + r;
        int minX = x - r;
        int maxY = y + r;
        int minY = y - r;

        int count = 0;

        for (int j = 0; j < pointsSize; ++j) {
            int px = points[j][0];
            int py = points[j][1];
            // 加速的判斷，是否有意義不好說，對于不符合的點會更快，對于符合的點會更慢，也許就互相抵消了
            if (px < minX || px > maxX
                || py < minY || py > maxY) {
                continue;
            }
            // 到圓心距離小于等于半徑的點就是滿足題目要求的點
            double dis = (px - x) * (px - x) + (py - y) * (py - y);
            if (dis <= r2) {
                ++count;
            }
        }

        ans[i] = count;
    }

    return ans;
}

c++

class Solution {
public:
    vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
        vector<int> ans;

        for (auto &query : queries) {
            int x = query[0];
            int y = query[1];
            int r = query[2];
            int r2 = r * r;
            int maxX = x + r;
            int minX = x - r;
            int maxY = y + r;
            int minY = y - r;

            int count = 0;

            for (auto &point : points) {
                int px = point[0];
                int py = point[1];
                // 加速的判斷，是否有意義不好說，對于不符合的點會更快，對于符合的點會更慢，也許就互相抵消了
                if (px < minX || px > maxX
                    || py < minY || py > maxY) {
                    continue;
                }
                // 到圓心距離小于等于半徑的點就是滿足題目要求的點
                double dis = (px - x) * (px - x) + (py - y) * (py - y);
                if (dis <= r2) {
                    ++count;
                }
            }

            ans.push_back(count);
        }

        return ans;
    }
};

python

class Solution:
    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
        ans = []

        for x, y, r in queries:
            r2 = r * r
            maxX = x + r
            minX = x - r
            maxY = y + r
            minY = y - r

            count = 0
            for px, py in points:
	            # 加速的判斷，是否有意義不好說，對于不符合的點會更快，對于符合的點會更慢，也許就互相抵消了
                if (px < minX or px > maxX
                        or py < minY or py > maxY):
                    continue
                # 到圓心距離小于等于半徑的點就是滿足題目要求的點
                dis = (px - x) ** 2 + (py - y) ** 2
                if dis <= r2:
                    count += 1

            ans.append(count)

        return ans

go

func countPoints(points [][]int, queries [][]int) []int {
    ans := make([]int, len(queries))

	for i, query := range queries {
		x := query[0]
		y := query[1]
		r := query[2]
		r2 := r * r
		maxX := x + r
		minX := x - r
		maxY := y + r
		minY := y - r

		for _, point := range points {
			px := point[0]
			py := point[1]
			// 加速的判斷，是否有意義不好說，對于不符合的點會更快，對于符合的點會更慢，也許就互相抵消了
			if px < minX || px > maxX || py < minY || py > maxY {
				continue
			}
			// 到圓心距離小于等于半徑的點就是滿足題目要求的點
			dis := (px - x) * (px - x) + (py - y) * (py - y)
			if dis <= r2 {
				ans[i]++
			}
		}
	}

	return ans
}

rust

impl Solution {
    pub fn count_points(points: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        queries.iter().map(|query| {
            let (x, y, r) = (query[0], query[1], query[2]);
            let r2 = r * r;
            let max_x = x + r;
            let min_x = x - r;
            let max_y = y + r;
            let min_y = y - r;

            points.iter().map(|point| {
                let (px, py) = (point[0], point[1]);
                if px >= min_x && px <= max_x
                    && py >= min_y && py <= max_y {
                    // 到圓心距離小于等于半徑的點就是滿足題目要求的點
                    let dis = (px - x) * (px - x) + (py - y) * (py - y);
                    if dis <= r2 {
                        return 1;
                    }
                }
                0
            }).sum()
        }).collect()
    }
}

原題傳送門