#!/usr/bin/env python3
from collections import namedtuple
from math import ceil, floor

Circle = namedtuple('Circle', 'x, y, r')


def count_lattice_points(r):
    """Count the number of lattice points inside a circle of radius *r*.

    https://e...content-available-to-author-only...a.org/wiki/Gauss_circle_problem
    """
    assert isinstance(r, int)
    return 1 + 4 * r + 4 * sum(int((r**2 - i**2)**.5) for i in range(1, r + 1))


def count_lattice_points_intersection(a, b):
    """The number of lattice points within intersection of circle *a* and *b*.

    x, y, r are all integers
    """
    # d = (a.x - b.x)**2 + (a.y - b.y)**2  # distance squared
    # if d > (a.r + b.r)**2:     # no intersection
    #     return 0
    # elif d == (a.r + b.r)**2:  # touch in one point
    #     # (y - a.y)/ a.r == (b.y - a.y) / (a.r + b.r)
    #     # (x - a.x)/ a.r == (b.x - a.x) / (a.r + b.r)
    #     return (a.r * (b.y - a.y) % (a.r + b.r) == 0 and
    #             a.r * (b.x - a.x) % (a.r + b.r) == 0)
    # elif d <= (a.r - b.r)**2:  # one circle within another
    #     return count_lattice_points(min(a.r, b.r))

    # # circumferences intersect in two points
    # assert (a.r - b.r)**2 < d < (a.r + b.r)**2
    if a.r > b.r:
        a, b = b, a  # make *a* be the smaller circle
    assert a.r <= b.r

    # scan from bottom to top
    count = 0
    for y in range(a.y - a.r, a.y + a.r + 1):
        if b.y - b.r <= y <= b.y + b.r:  # intersection possible
            # find intersection boundaries for given y
            ax1, ax2 = x_coordinates_intesect(a, y)
            bx1, bx2 = x_coordinates_intesect(b, y)
            if min(ax2, bx2) >= max(ax1, bx1):  # intersect
                count += floor(min(ax2, bx2)) - ceil(max(ax1, bx1)) + 1
    return count


def count_lattice_points_intersection_bruteforce(a, b):
    return sum(((a.x - x)**2 + (a.y - y)**2 <= a.r**2 and
                (b.x - x)**2 + (b.y - y)**2 <= b.r**2)
               for y in range(a.y - a.r, a.y + a.r + 1)
               for x in range(a.x - a.r, a.x + a.r + 1))


def x_coordinates_intesect(c, y):
    """Get x-coordinates of intersection of circle *c* and horizontal line *y*."""
    # solve quadratic equation
    # (x - c.x)**2 + (y - c.y)**2 == c.r**2
    assert c.r**2 >= (y - c.y)**2
    D = (c.r**2 - (y - c.y)**2)**.5
    return c.x - D, c.x + D

print(count_lattice_points_intersection(Circle(0, 0, 5), Circle(2, 2, 3)))

for a, b in [
        (Circle(0, 0, 5), Circle(2, 2, 3)),
        (Circle(0, 0, 4), Circle(2, 2, 3)),
        (Circle(0, 0, 6), Circle(2, 2, 3)),
]:
    got = count_lattice_points_intersection(a, b)
    expected = count_lattice_points_intersection_bruteforce(a, b)
    assert got == expected, (a, b, got, expected)