2249. Count Lattice Points Inside a Circle Medium
1/**
2 * [2249] Count Lattice Points Inside a Circle
3 *
4 * Given a 2D integer array circles where circles[i] = [xi, yi, ri] represents the center (xi, yi) and radius ri of the i^th circle drawn on a grid, return the number of lattice points that are present inside at least one circle.
5 * Note:
6 *
7 * A lattice point is a point with integer coordinates.
8 * Points that lie on the circumference of a circle are also considered to be inside it.
9 *
10 *
11 * Example 1:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/exa-11.png" style="width: 300px; height: 300px;" />
13 * Input: circles = [[2,2,1]]
14 * Output: 5
15 * Explanation:
16 * The figure above shows the given circle.
17 * The lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.
18 * Other points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.
19 * Hence, the number of lattice points present inside at least one circle is 5.
20 * Example 2:
21 * <img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/exa-22.png" style="width: 300px; height: 300px;" />
22 * Input: circles = [[2,2,2],[3,4,1]]
23 * Output: 16
24 * Explanation:
25 * The figure above shows the given circles.
26 * There are exactly 16 lattice points which are present inside at least one circle.
27 * Some of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).
28 *
29 *
30 * Constraints:
31 *
32 * 1 <= circles.length <= 200
33 * circles[i].length == 3
34 * 1 <= xi, yi <= 100
35 * 1 <= ri <= min(xi, yi)
36 *
37 */
38
39pub struct Solution {}
40use std::collections::HashSet;
41// problem: https://leetcode.com/problems/count-lattice-points-inside-a-circle/
42// discuss: https://leetcode.com/problems/count-lattice-points-inside-a-circle/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47 pub fn count_lattice_points(circles: Vec<Vec<i32>>) -> i32 {
48 let mut set: HashSet<(i32, i32)> = HashSet::new();
49
50 for circle in circles {
51 for x in circle[0] - circle[2]..circle[0] + circle[2] + 1 {
52 for y in circle[1] - circle[2]..circle[1] + circle[2] + 1 {
53 if set.contains(&(x, y)) {
54 continue
55 }
56
57 if Self::in_circle(&circle, (x, y)) {
58 set.insert((x, y));
59 }
60 }
61 }
62 }
63
64 set.len() as i32
65 }
66
67 fn in_circle(circle: &Vec<i32>, point: (i32, i32)) -> bool {
68 let c: i64 = (circle[2] as i64).pow(2);
69 return (point.0 as i64 - circle[0] as i64).pow(2) + (point.1 as i64 - circle[1] as i64).pow(2) <= c;
70 }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77 use super::*;
78
79 #[test]
80 fn test_2249_1() {
81 assert_eq!(Solution::count_lattice_points(vec!(vec!(2,2,1))), 5)
82 }
83}
84
Back
© 2025 bowen.ge All Rights Reserved.