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

from collections import deque, defaultdict


class Solution:
    def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool:

        def check_start(x, y, r):
            if pow(r, 2) - pow(Y - y, 2) >= 0:
                cand1 = (pow(r, 2) - pow(Y - y, 2)) ** 0.5 + x
                cand2 = -((pow(r, 2) - pow(Y - y, 2)) ** 0.5) + x
            else:
                cand1 = float("inf")
                cand2 = float("inf")
            if pow(r, 2) - pow(-x, 2) >= 0:
                cand3 = (pow(r, 2) - pow(-x, 2)) ** 0.5 + y
                cand4 = -((pow(r, 2) - pow(-x, 2)) ** 0.5) + y
            else:
                cand3 = float("inf")
                cand4 = float("inf")
            if cand1 == cand2 == cand3 == cand4 == float("inf"):
                return False
            return (
                0 <= cand1 <= X
                or 0 <= cand2 <= X
                or 0 <= cand3 <= Y
                or 0 <= cand4 <= Y
                or (0 <= x <= X and 0 <= y <= Y)
            )

        def check_end(x, y, r):
            if pow(r, 2) - pow(-y, 2) >= 0:
                cand1 = (pow(r, 2) - pow(-y, 2)) ** 0.5 + x
                cand2 = -((pow(r, 2) - pow(-y, 2)) ** 0.5) + x
            else:
                cand1 = float("inf")
                cand2 = float("inf")
            if pow(r, 2) - pow(X - x, 2) >= 0:
                cand3 = (pow(r, 2) - pow(X - x, 2)) ** 0.5 + y
                cand4 = -((pow(r, 2) - pow(X - x, 2)) ** 0.5) + y
            else:
                cand3 = float("inf")
                cand4 = float("inf")
            if cand1 == cand2 == cand3 == cand4 == float("inf"):
                return False
            return (
                0 <= cand1 <= X
                or 0 <= cand2 <= X
                or 0 <= cand3 <= Y
                or 0 <= cand4 <= Y
                or (0 <= x <= X and 0 <= y <= Y)
            )

        def check_intersecton(x1, y1, r1, x2, y2, r2):
            d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
            if d > r1 + r2 or d < abs(r1 - r2):
                return False

            if d == 0 and r1 == r2:
                return False

            a = (r1**2 - r2**2 + d**2) / (2 * d)
            h = math.sqrt(r1**2 - a**2)

            x3 = x1 + a * (x2 - x1) / d
            y3 = y1 + a * (y2 - y1) / d

            x4 = x3 + h * (y2 - y1) / d
            y4 = y3 - h * (x2 - x1) / d

            x5 = x3 - h * (y2 - y1) / d
            y5 = y3 + h * (x2 - x1) / d
            # print(x4, y4, x5, y5)
            return (0 <= x4 <= X and 0 <= y4 <= Y) or (0 <= x5 <= X and 0 <= y5 <= Y)

        n = len(circles)
        queue = deque([])
        G = defaultdict(list)
        seen = set()
        for i in range(n):
            x1, y1, r1 = circles[i]
            if check_start(x1, y1, r1):
                queue.append(i)
                seen.add(i)
            for j in range(i):
                x2, y2, r2 = circles[j]
                if check_intersecton(x1, y1, r1, x2, y2, r2):
                    G[i].append(j)
                    G[j].append(i)
        while queue:
            curr = queue.popleft()
            x, y, r = circles[curr]
            if check_end(x, y, r):
                return False
            for adj in G[curr]:
                if adj not in seen:
                    queue.append(adj)
                    seen.add(adj)
        return True

29640