<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, self.X, self.Y = len(circles), X, Y
        uf = UnionFind(n+2)

        for i in range(n):
            x1, y1, r1 = circles[i]
            if x1**2 + y1**2 <= r1**2 or (x1-X)**2 + (y1-Y)**2 <= r1**2:
                # (0,0) or (X,Y) in the circle
                return False
            if x1 >= X and y1 >= Y or x1 >= X+r1 or y1 >= Y+r1:
                # completely off the rectangle
                continue
            if x1**2 + (y1-Y)**2 <= r1**2 or x1 <= r1 and 0 <= y1 <= Y or abs(y1-Y) <= r1 and 0 <= x1 <= X:
                # union with the top&left edges
                uf.union(i, n)
            if (x1-X)**2 + y1**2 <= r1**2 or y1 <= r1 and 0 <= x1 <= X or abs(x1-X) <= r1 and 0 <= y1 <= Y:
                # union with the bottom&right edges
                uf.union(i, n+1)
            for j in range(i+1, n):
                if self.checkCross(circles[i], circles[j]):
                    # intersect in the rectangle
                    uf.union(i, j)

        return uf.find(n) != uf.find(n+1)

    def checkCross(self, circle1: List[int], circle2: List[int]) -> bool:
        (x1, y1, r1), (x2, y2, r2) = circle1, circle2

        # squared distance betwen the two centres
        r = (x1-x2)**2 + (y1-y2)**2
        if r <= (r1-r2)**2 or r > (r1+r2)**2:
            # not connected or one inside the other
            return False

        rr = (r1**2-r2**2)/(2*r)
        delta = (r1**2+r2**2)/(2*r) - rr**2 - 0.25
        if delta < 1e-9:
            # two circles in touch
            delta = 0
        dr = sqrt(delta)

        # coordinates of the intersection points
        cx1, cy1 = (x1+x2)/2 + rr * (x2-x1) + dr * (y2-y1), (y1+y2)/2 + rr * (y2-y1) + dr * (x1-x2)
        cx2, cy2 = (x1+x2)/2 + rr * (x2-x1) - dr * (y2-y1), (y1+y2)/2 + rr * (y2-y1) - dr * (x1-x2)
        
        # check if any of the intersection points in the rectangle
        return (0 <= cx1 <= self.X) and (0 <= cy1 <= self.Y) or (0 <= cx2 <= self.X) and (0 <= cy2 <= self.Y)


class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0]*n

    def find(self, node: int) -> int:
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1: int, node2: int):
        r1, r2 = self.find(node1), self.find(node2)
        if r1 != r2:
            if self.rank[r1] < self.rank[r2]:
                self.parent[r1] = r2
            else:
                self.parent[r2] = r1
                if self.rank[r1] == self.rank[r2]:
                    self.rank[r1] += 1
17859