2249-统计圆内格点数目

给你一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为
ri 的第 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 <= xi, yi <= 100
• 1 <= ri <= min(xi, yi)

先按半径从大到小排序，这样可以更早地遇到包含当前枚举的点的圆。

[sol1-Python3]

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

[sol1-Go]

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
}