统计圆内格点数目

2249. 统计圆内格点数目

给你一个二维整数数组 circles ，其中 circles[i] = [x_i, y_i, r_i] 表示网格上圆心为 (x_i, y_i) 且半径为 r_i 的第 i 个圆，返回出现在 至少一个 圆内的 格点数目 。

注意：

格点是指整数坐标对应的点。
圆周上的点 也被视为出现在圆内的点。

示例 1：

输入：circles = [[2,2,1]]
输出：5
解释：
给定的圆如上图所示。
出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2)，在图中用绿色标识。
像 (1, 1) 和 (1, 3) 这样用红色标识的点，并未出现在圆内。
因此，出现在至少一个圆内的格点数目是 5 。

示例 2：

输入：circles = [[2,2,2],[3,4,1]]
输出：16
解释：
给定的圆如上图所示。
共有 16 个格点出现在至少一个圆内。
其中部分点的坐标是 (0, 2)、(2, 0)、(2, 4)、(3, 2) 和 (4, 4) 。

提示：

1 <= circles.length <= 200
circles[i].length == 3
1 <= x_i, y_i <= 100
1 <= r_i <= min(x_i, y_i)

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int countLatticePoints(vector<vector<int>>& circles) { } };

golang 解法, 执行用时: 44 ms, 内存消耗: 2.1 MB, 提交时间: 2023-01-09 15:31:33

func countLatticePoints(circles [][]int) (ans int) {
	// 按半径从大到小排序，这样能更早遇到包含 (x,y) 的圆
	sort.Slice(circles, func(i, j int) bool { return circles[i][2] > circles[j][2] })
	for x := 0; x <= 200; x++ {
		for y := 0; y <= 200; y++ {
			for _, c := range circles {
				// 判断 (x,y) 是否在圆 c 内
				if (x-c[0])*(x-c[0])+(y-c[1])*(y-c[1]) <= c[2]*c[2] {
					ans++
					break
				}
			}
		}
	}
	return
}

python3 解法, 执行用时: 844 ms, 内存消耗: 14.9 MB, 提交时间: 2023-01-09 15:31:15

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        ans = 0
        circles.sort(key=lambda c: -c[2])  # 按半径从大到小排序，这样能更早遇到包含 (i,j) 的圆
        max_x = max(c[0] + c[2] for c in circles)
        max_y = max(c[1] + c[2] for c in circles)
        for i in range(max_x + 1):
            for j in range(max_y + 1):
                for x, y, r in circles:
                    if (x - i) * (x - i) + (y - j) * (y - j) <= r * r:
                        ans += 1
                        break
        return ans

上一题

下一题

详情