Grid Points Under Circles

Medium

Circles are drawn on a grid: circles[i] = [x, y, r] is a circle centred at (x, y) with radius r. Return the number of points with integer coordinates that lie inside at least one circle. A point on a circle's boundary counts as inside.

Example 1

circles=[[1, 1, 1]] → 5

The circle centred at (1, 1) with radius 1 covers the centre and (0, 1), (2, 1), (1, 0), (1, 2): 5 points.

Example 2

circles=[[1, 1, 1], [2, 1, 1]] → 8

The second circle adds (3, 1), (2, 0) and (2, 2); its other points are already counted. Total 8.

Example 3

circles=[[5, 5, 2]] → 13

Constraints

1 ≤ len(circles) ≤ 200
each circles[i] has three numbers
1 ≤ x, y ≤ 100
1 ≤ r ≤ min(x, y)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Geometry Array Hash Table Math Enumeration

Similar problems

Smallest Paddock Medium Fewest Lines Through the Dots Medium Empty Boxes Between Points Medium Primes Along Grid Rays Medium Empty Rectangle From Marked Points Medium

Input

circles=[[1, 1, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 85 tests on the server, hidden ones included.