Count Lattice Points Inside a Circle

To solve this problem, we’ll use a brute force approach. We need to find all the lattice points (integer coordinates) that fall inside any of the given circles. A point (x, y) is inside a circle centered at (x_center, y_center) with a radius of r if the distance between the point and the center of the circle is less than or equal to r. The Euclidean distance formula can be used to find the distance.

Python Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def countLatticePoints(self, circles: List[List[int]]) -> int:
        min_x = min(x-r for x, y, r in circles)
        max_x = max(x+r for x, y, r in circles)
        min_y = min(y-r for x, y, r in circles)
        max_y = max(y+r for x, y, r in circles)

        lattice_points = set()
        for x in range(min_x, max_x+1):
            for y in range(min_y, max_y+1):
                for x_center, y_center, r in circles:
                    if (x - x_center)**2 + (y - y_center)**2 <= r**2:
                        lattice_points.add((x, y))
                        break
        return len(lattice_points)

This solution iterates over each point in the smallest rectangle that can cover all circles. For each point, it checks if the point is inside any of the circles. If it is, it adds it to the set of lattice points (avoiding duplicates) and breaks the inner loop to move on to the next point. Finally, it returns the size of the set of lattice points.

The time complexity is proportional to the area of the rectangle covering all circles, and hence, can be quite high for large inputs. It’s also proportional to the number of circles. The space complexity is proportional to the number of lattice points inside the circles.