<p>Given a 2D integer array <code>circles</code> where <code>circles[i] = [x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub>]</code> represents the center <code>(x<sub>i</sub>, y<sub>i</sub>)</code> and radius <code>r<sub>i</sub></code> of the <code>i<sup>th</sup></code> circle drawn on a grid, return <em>the <strong>number of lattice points</strong> </em><em>that are present inside <strong>at least one</strong> circle</em>.</p>

<p><strong>Note:</strong></p>

<ul>
	<li>A <strong>lattice point</strong> is a point with integer coordinates.</li>
	<li>Points that lie <strong>on the circumference of a circle</strong> are also considered to be inside it.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/exa-11.png" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> circles = [[2,2,1]]
<strong>Output:</strong> 5
<strong>Explanation:</strong>
The figure above shows the given circle.
The lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.
Other points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.
Hence, the number of lattice points present inside at least one circle is 5.</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/02/exa-22.png" style="width: 300px; height: 300px;" />
<pre>
<strong>Input:</strong> circles = [[2,2,2],[3,4,1]]
<strong>Output:</strong> 16
<strong>Explanation:</strong>
The figure above shows the given circles.
There are exactly 16 lattice points which are present inside at least one circle. 
Some of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= circles.length &lt;= 200</code></li>
	<li><code>circles[i].length == 3</code></li>
	<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 100</code></li>
	<li><code>1 &lt;= r<sub>i</sub> &lt;= min(x<sub>i</sub>, y<sub>i</sub>)</code></li>
</ul>

import math
class Solution:
    def inside_circle(self, i, j, x, y, r):
        return math.sqrt(abs(y - j) ** 2 + abs(x - i) ** 2) <= r

    def countLatticePoints(self, circles: List[List[int]]) -> int:
        all_points = set()
        for x, y, r in circles:
            for i in range(x-r, x+r+1):
                for j in range(y-r, y+r+1):
                    if self.inside_circle(i, j, x, y, r):
                        all_points.add((i, j))
        return len(all_points)

"""

goal: # lattice points (int coords) present inside at least one circle (including on circ), all circles are integer array

intuitions:


approach:
- points: r=1:l=5(1+3+1), r=2:l=13(1+3+5+3+1), r=3:l=(1+3+5+7+5+3+1) = 25. can get closed formula: 2r+1+ ((1 + 2r - 1)*r)
- problem: overlaping circles
- one way: add points to set and count set; bad because quadratic. 
- goal: intelligently ignore overlaps
- how to determine number of overlapping points? (1,1) can only intersect at point. (1, 2) intersect at 3. what about (2,2)? 2. can probably have closed formula that takes (dist, r1, r2) and returns (overlap). suppose we have this formula. 
- algorithm assuming we have this formula: go through each circle, add ricle points through formula 1, subtract circle overlaps through other formulas. still n^2 since every circle with every other circle...


hint: how to check whether lattice point inside circle? based on radius. basically calculate distance. 
hint: reduce search space, min and max values of lattice point of circle


"""
2395