from math import hypot, acos, cos, sin, pi, atan2


class _Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return f"({self.x}, {self.y})"

    def __add__(self, other):
        return _Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return _Point(self.x - other.x, self.y - other.y)

    def __neg__(self):
        return _Point(-self.x, -self.y)

    def __rmul__(self, k):
        return _Point(k * self.x, k * self.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y


class Segment:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2

    def length(self):
        return hypot(self.p1.x - self.p2.x, self.p1.y - self.p2.y)

    def __repr__(self):
        return f"Segment {self.p1} --- {self.p2}"

    # returns True if the segment intersect a Circle
    def intersect(self, circle):
        u = (
            (self.p2.x - self.p1.x) * (circle.center.x - self.p1.x)
            + (self.p2.y - self.p1.y) * (circle.center.y - self.p1.y)
        ) / self.length() ** 2
        # pt: the shortest point of segment [p1, p2] to the center of the circle
        pt = self.p1 + max(0, min(u, 1)) * (self.p2 - self.p1)

        seg = Segment(circle.center, pt)
        # Some threshold to prevent approximation errors
        return circle.radius - seg.length() > 1e-6


class _Circle:
    def __init__(self, center, radius):
        self.center = center
        self.radius = radius

    def __repr__(self):
        return f"_Circle of center {self.center} and radius {self.radius}"

    def __eq__(self, other):
        return self.center.x == other.center.x and self.center.y == other.center.y and self.radius == other.radius
        

    # gets the intersection with another circle
    def intersect(self, other):
        assert type(other) == _Circle, "Element is not a circle"
        ca, cb = self.center, other.center
        ra, rb = self.radius, other.radius
        d = Segment(ca, cb).length()
        # No intersction
        if ra + rb < d or abs(ra - rb) > d:
            return (False, [])
        a = (ra**2 + d**2 - rb**2) / (2 * d)
        # 1 intersection point
        if abs(a - ra) <= 1e-6:
            c = ca + a / d * (cb - ca)
            return (False, [c])
        # 2 intersection points
        d = ca + ra / d * (cb - ca)
        u = max(-1, min(a / ra, 1))
        t = acos(u)
        p = _Point(
            ca.x + cos(t) * (d.x - ca.x) - sin(t) * (d.y - ca.y),
            ca.y + sin(t) * (d.x - ca.x) + cos(t) * (d.y - ca.y),
        )
        q = _Point(
            ca.x + cos(t) * (d.x - ca.x) + sin(t) * (d.y - ca.y),
            ca.y - sin(t) * (d.x - ca.x) + cos(t) * (d.y - ca.y),
        )
        return (True, [p, q])

class Rectangle:
    def __init__(self, x, y, w, h):
        self.x = x
        self.y = y        
        self.w = w 
        self.h = h
    
    def __repr__(self):
        return f"Rectangle at x = {self.x} and y = {self.y} of width {self.w} and height {self.h}"
    
    def rectangle_intersect(self, other):
        return not (self.x + self.w < other.x
                or self.x > other.x + other.w
                or self.y + self.h < other.y
                or self.y > other.y + other.h)

    def circle_intersect(self, other):        
        c = other.center
        cx = max(self.x, min(self.x + self.w, c.x))
        cy = max(self.y, min(self.y + self.h, c.y))
        sq2 = (c.x - cx)**2 + (c.y - cy)**2    
        return sq2 < other.radius**2


class QuadTree:
    def __init__(self, rectangle):
        self.is_leaf = False
        self.rectangle  = rectangle
        self.circles = None # not None only if the node is leaf
        self.NW = None
        self.NE = None
        self.SW = None
        self.SE = None

def build_rect_bounds(circles_lst):
    xmin, xmax = float('inf'), float('-inf')
    ymin, ymax = float('inf'), float('-inf')
    for circle in circles_lst:
        x, y, r = circle.center.x, circle.center.y, circle.radius
        xmin = min(x - r, xmin)
        ymin = min(y - r, ymin)
        xmax = max(x + r, xmax)
        ymax = max(y + r, ymax)
    width, height = xmax - xmin, ymax - ymin
    return Rectangle(xmin, ymin, width, height)

def build_quad_tree(rect, circles_lst, size=6):
    circles = []
    for circle in circles_lst:
        if rect.circle_intersect(circle):
            circles.append(circle)
    node = QuadTree(rect)
    # print("Circles length ", len(circles))
    if len(circles) <= size:
        node.circles = circles
        node.is_leaf = True
        return node
    w, h = rect.w / 2, rect.h / 2
    if len(circles) > size:
        print(len(circles), rect.w, rect.h)
    node.NW = build_quad_tree(Rectangle(rect.x, rect.y + h, w, h), circles, size)
    node.NE = build_quad_tree(Rectangle(rect.x + w, rect.y + h, w, h), circles, size)
    node.SW = build_quad_tree(Rectangle(rect.x, rect.y, w, h), circles, size)
    node.SE = build_quad_tree(Rectangle(rect.x + w, rect.y, w, h), circles, size)
    return node

# returns True if the point corresponding to the angle x lies between the points corresponding to angles a and b
def is_between_angles(x, a, b):
    a %= 2 * pi
    b %= 2 * pi
    x %= 2 * pi
    delta = (b - a) % (2 * pi)
    if delta <= pi:
        return (x - a) % (2 * pi) <= delta
    else:
        return (a - x) % (2 * pi) <= (2 * pi - delta)


# Returns the angle between the x-axis and vector(center, pt)
def angle(center, pt):
    return atan2(pt.y - center.y, pt.x - center.x)

# Checks if an arc p->q lying on "circle" intersects "other" (=another circle)
def arc_is_good(p, q, circle, other):
    b, pts = other.intersect(circle)
    if not b:
        return True
    center = other.center
    t1 = angle(center, p)
    t2 = angle(center, q)
    # if any of the intersection lies between t1 and t2, the segment is not valid
    if any(is_between_angles(angle(center, pt), t1, t2) for pt in pts):
        return False
    return True

# Checks recursively if an arc p->q lying on "circle" intersects quad tree "node"             
def is_arc_clear(node, p, q, circle):
    x, y, r = circle.center.x, circle.center.y, circle.radius
    rect = Rectangle(x - r, y - r, 2 * r, 2 * r)
    node_rect = node.rectangle
    if not rect.rectangle_intersect(node_rect):
        return True
    if node.is_leaf:
        for other in node.circles:
            # No need to check since p anq q are lying on "circle"
            if other == circle:
                continue
            if not arc_is_good(p, q, circle, other):
                return False
        return True
    if not is_arc_clear(node.NW, p, q, circle):
        return False
    if not is_arc_clear(node.NE, p, q, circle):
        return False
    if not is_arc_clear(node.SW, p, q, circle):
        return False
    if not is_arc_clear(node.SE, p, q, circle):
        return False
    return True


def test_circle_circle_intersections():
    c1 = _Circle(_Point(0,0), 1)
    c2 = _Circle(_Point(2,0), 1)
    b, pts = c1.intersect(c2)
    assert b is False and len(pts) == 1   # tangent
    c3 = _Circle(_Point(3,0), 1)
    b, pts = c1.intersect(c3)
    assert b is False and pts == []      # disjoint
    c4 = _Circle(_Point(1,0), 1)
    b, pts = c1.intersect(c4)
    assert len(pts) == 2                 # 2 points

def test_rectangle_intersections():
    r1 = Rectangle(0,0,2,2)
    r2 = Rectangle(1,1,2,2)
    assert r1.rectangle_intersect(r2)    # overlap
    r3 = Rectangle(3,3,1,1)
    assert not r1.rectangle_intersect(r3) # disjoint

def test_circle_rectangle_intersections():
    r = Rectangle(0,0,2,2)
    c1 = _Circle(_Point(1,1), 0.5)
    c2 = _Circle(_Point(5,5), 1)
    assert r.circle_intersect(c1)
    assert not r.circle_intersect(c2)

def test_quadtree_building():
    circles = [
        _Circle(_Point(1,1), 0.5),
        _Circle(_Point(4,4), 0.5),
        _Circle(_Point(8,8), 1),
    ]
    bounds = build_rect_bounds(circles)
    
    root = build_quad_tree(bounds, circles, size=1)
    assert root.NW and root.NE and root.SW and root.SE

def test_is_arc_clear_simple():
    c1 = _Circle(_Point(0,0), 5)
    c2 = _Circle(_Point(3,0), 1)
    circles = [c1, c2]
    rect = build_rect_bounds(circles)
    print("Bounds: ", rect)
    root = build_quad_tree(rect, circles, size=1)

    # arc on c1 from leftmost to topmost point
    p = _Point(-5,0)
    q = _Point(0,5)
    assert not is_arc_clear(root, p, q, c1)  # blocked by c2

    # arc on c1 far from c2
    p = _Point(-5,0)
    q = _Point(0,-5)
    assert is_arc_clear(root, p, q, c1)


test_circle_circle_intersections()
test_rectangle_intersections()
test_circle_rectangle_intersections()
test_quadtree_building()
test_is_arc_clear_simple()
print("All tests passed!")