<p>You are given two positive integers <code>xCorner</code> and <code>yCorner</code>, and a 2D array <code>circles</code>, where <code>circles[i] = [x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub>]</code> denotes a circle with center at <code>(x<sub>i</sub>, y<sub>i</sub>)</code> and radius <code>r<sub>i</sub></code>.</p>

<p>There is a rectangle in the coordinate plane with its bottom left corner at the origin and top right corner at the coordinate <code>(xCorner, yCorner)</code>. You need to check whether there is a path from the bottom left corner to the top right corner such that the <strong>entire path</strong> lies inside the rectangle, <strong>does not</strong> touch or lie inside <strong>any</strong> circle, and touches the rectangle <strong>only</strong> at the two corners.</p>

<p>Return <code>true</code> if such a path exists, and <code>false</code> otherwise.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">xCorner = 3, yCorner = 4, circles = [[2,1,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example2circle1.png" style="width: 346px; height: 264px;" /></p>

<p>The black curve shows a possible path between <code>(0, 0)</code> and <code>(3, 4)</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">xCorner = 3, yCorner = 3, circles = [[1,1,2]]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example1circle.png" style="width: 346px; height: 264px;" /></p>

<p>No path exists from <code>(0, 0)</code> to <code>(3, 3)</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">xCorner = 3, yCorner = 3, circles = [[2,1,1],[1,2,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example0circle.png" style="width: 346px; height: 264px;" /></p>

<p>No path exists from <code>(0, 0)</code> to <code>(3, 3)</code>.</p>
</div>

<p><strong class="example">Example 4:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">xCorner = 4, yCorner = 4, circles = [[5,5,1]]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2024/08/04/rectangles.png" style="width: 346px; height: 264px;" /></p>
</div>

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

<ul>
	<li><code>3 &lt;= xCorner, yCorner &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= circles.length &lt;= 1000</code></li>
	<li><code>circles[i].length == 3</code></li>
	<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub>, r<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
</ul>

"""
Idea: make a graph where nodes are each circle, and also the top left lines, and bottom right lines

If a circle intersects with another circle/line, add an edge between them

There is a path iff the circles intersect/have edges such that they connect the top left and bottom left
edges of the rectangle
"""

class Solution:
    def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool:
        # circles
        def dist(x1, y1, x2, y2):
            xx = x1 - x2
            yy = y1 - y2
            return sqrt(xx*xx + yy*yy)

        def intersect(a, b):
            return dist(a[0], a[1], b[0], b[1]) <= a[2] + b[2]
        
        def intersect_v(c, x, h):
            if c[1] <= h and c[1] >= 0:
                return abs(c[0] - x) <= c[2]
            return dist(c[0], c[1], x, 0) <= c[2] or dist(c[0], c[1], x, h) <= c[2]
        
        def intersect_h(c, y, l):
            if c[0] <= l and c[0] >= 0:
                return abs(c[1] - y) <= c[2]
            return dist(c[0], c[1], 0, y) <= c[2] or dist(c[0], c[1], l, y) <= c[2]
        
        g = defaultdict(set)

        for i, a in enumerate(circles):
            for j, b in enumerate(circles):
                if i != j and intersect(a,b):
                    g[i].add(j)
                    g[j].add(i)
        
        # check intersect with lines
        for i, a in enumerate(circles):
            if intersect_v(a, 0, Y) or intersect_h(a, Y, X):
                g[i].add("tl")
                g["tl"].add(i)
            if intersect_v(a, X, Y) or intersect_h(a, 0, X):
                g[i].add("br")
                g["br"].add(i)
        
        # bfs
        def bfs(source, target):
            visited = defaultdict(lambda: False)
            visited[source] = True

            queue = [source]

            while queue:
                cur = queue.pop(0)

                if cur == target:
                    return True
                
                for i in g[cur]:
                    if not visited[i]:
                        queue.append(i)
                        visited[i] = True
            return False

        return not bfs("tl", "br")
61359