<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>

class Solution:
    def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:
        topleft = -1
        bottomright = -2

        graph = collections.defaultdict(list)
        for j, (x0, y0, r0) in enumerate(circles):
            if x0 ** 2 + y0 ** 2 <= r0 ** 2:
                return False
            if (x0 - xCorner) ** 2 + (y0 - yCorner) ** 2 <= r0 ** 2:
                return False
            if self.connect_to_topleft(x0, y0, r0, xCorner, yCorner):
                graph[j].append(topleft)
                graph[topleft].append(j)
            if self.connect_to_bottomright(x0, y0, r0, xCorner, yCorner):
                graph[j].append(bottomright)
                graph[bottomright].append(j)
            for k, (x1, y1, r1) in enumerate(circles[:j]):
                if self.connect_circles(x0, y0, r0, x1, y1, r1, xCorner, yCorner):
                    graph[j].append(k)
                    graph[k].append(j)
        
        stack = [topleft]
        seen = set()
        while stack:
            node = stack.pop()
            if node in seen:
                continue
            seen.add(node)
            if node == bottomright:
                return False
            for nbr in graph[node]:
                stack.append(nbr)
        return True
        
    def connect_to_topleft(self, x0, y0, r0, xCorner, yCorner):
        if x0 ** 2 + (y0 - yCorner) ** 2 <= r0 ** 2:
            return True
        if abs(x0) <= r0 and 0 <= y0 <= yCorner:
            return True
        if abs(y0 - yCorner) <= r0 and 0 <= x0 <= xCorner:
            return True
        return False
    
    def connect_to_bottomright(self, x0, y0, r0, xCorner, yCorner):
        if (x0 - xCorner) ** 2 + y0 ** 2 <= r0 ** 2:
            return True
        if abs(y0) <= r0 and 0 <= x0 <= xCorner:
            return True
        if abs(x0 - xCorner) <= r0 and 0 <= y0 <= yCorner:
            return True
        return False

    def connect_circles(self, x0, y0, r0, x1, y1, r1, xCorner, yCorner):
        if (x1 - x0) ** 2 + (y1 - y0) ** 2 > (r0 + r1) ** 2:
            return False
        if x0 <= xCorner and x1 <= xCorner:
            return True
        if y0 <= yCorner and y1 <= yCorner:
            return True
        if x0 == x1:
            return True
        if x0 > x1:
            x0, x1 = x1, x0
            y0, y1 = y1, y0
        d0 = ((yCorner - y0) ** 2 + (xCorner - x0) ** 2) ** 0.5
        d1 = ((yCorner - y1) ** 2 + (xCorner - x1) ** 2) ** 0.5
        if (yCorner - y0) * (x1 - x0) >= (y1 - y0) * (xCorner - x0):
            return True
        # if line goes through rectangle: return True
        # if path through corner works: return True
        return False
40515