<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, X: int, Y: int, circles: List[List[int]]) -> bool:
        n = len(circles)
        adj = [set() for _ in range(n + 2)]
        for i1, c1 in enumerate(circles):
            r1_sq = c1[2] ** 2
            if c1[2] ** 2 >= c1[0] ** 2 + c1[1] ** 2:
                return False
            elif c1[2] ** 2 >= (c1[0] - X) ** 2 + (c1[1] - Y) ** 2:
                return False
            b = False
            if (0 <= c1[0] <= X and (abs(c1[0]) <= c1[2] or abs(Y - c1[1]) <= c1[2])) or ((c1[0] ** 2 + (Y - c1[1]) ** 2) <= r1_sq):
                adj[i1].add(n)
                adj[n].add(i1)
            if (0 <= c1[1] <= Y and (abs(c1[1]) <= c1[2] or abs(X - c1[0]) <= c1[2])) or (((X - c1[0]) ** 2 + c1[1] ** 2) <= r1_sq):
                adj[i1].add(n + 1)
                adj[n + 1].add(i1)
            for i2 in range(i1):
                c2 = circles[i2]
                if c1[0] == c2[0] and c1[1] == c2[1]:
                    adj[i1].add(i2)
                    adj[i2].add(i1)
                    continue
                d_sq = ((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2)
                if d_sq <= (c1[2] + c2[2]) ** 2:
                    if 0 <= c1[0] <= X and 0 <= c1[1] <= Y and 0 <= c2[0] <= X and 0 <= c2[1] <= Y:
                        adj[i1].add(i2)
                        adj[i2].add(i1)
                        continue
                    # from https://math.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect
                    r2_sq = c2[2] ** 2
                    l_mul_2d = r1_sq - r1_sq + d_sq
                    h_mul_2d_allsq = r1_sq * 4 * d_sq - l_mul_2d ** 2
                    if h_mul_2d_allsq < 0: continue
                    d = math.sqrt(d_sq)
                    l = l_mul_2d / (2 * d)
                    h = math.sqrt(h_mul_2d_allsq) / (2 * d)
                    
                    if (0 <= ((l * (c2[0] - c1[0]) + h * (c2[1] - c1[1])) / d + c1[0]) <= X and 0 <= ((l * (c2[1] - c1[1]) - h * (c2[0] - c1[0])) / d + c1[1]) <= Y) or\
                            (0 <= ((l * (c2[0] - c1[0]) - h * (c2[1] - c1[1])) / d + c1[0]) <= X and 0 <= ((l * (c2[1] - c1[1]) + h * (c2[0] - c1[0])) / d + c1[1]) <= Y):
                        adj[i1].add(i2)
                        adj[i2].add(i1)
        #print(adj)
        seen = {n}
        stk = [n]
        while stk:
            i1 = stk.pop()
            for i2 in adj[i1]:
                if i2 in seen: continue
                elif i2 == n + 1: return False
                seen.add(i2)
                stk.append(i2)
        return True


55921