<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)
        dsu = DSU(N + 2)
        # N: left and top
        # N+1: right and bot

        def inter_circles(x1, y1, r1, x2, y2, r2):
            if x1 == x2 and y1 == y2:
                return 1

            d = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
            w = (r1**2 - r2**2 + d**2) / (2 * d)
            h = (r1**2 - w**2) ** 0.5

            if isinstance(h, complex):
                return 0

            x, xp = x1 + w / d * (x2 - x1), h / d * (y2 - y1)
            y, yp = y1 + w / d * (y2 - y1), -h / d * (x2 - x1)
            return (
                0 <= x + xp <= X and 0 <= y + yp <= Y or
                0 <= x - xp <= X and 0 <= y - yp <= Y
            )

        def inter_circle_seg(xc, yc, rc, x1, y1, x2, y2):
            assert x1 <= x2 and y1 <= y2

            if y1 == y2:  # horizontal segment
                B = -2 * xc
                C = xc**2 + (y1 - yc)**2 - rc**2
                radical = (B * B - 4 * C) ** 0.5
                if isinstance(radical, complex):
                    return 0
                x_left = (-B - radical) / 2.0
                x_right = (-B + radical) / 2.0
                return max(x_left, x1) <= min(x_right, x2)

            return inter_circle_seg(yc, xc, rc, y1, x1, y2, x2)


        for i, (x1, y1, r1) in enumerate(circles):
            for j in range(i + 1, N):
                x2, y2, r2 = circles[j]
                if inter_circles(x1, y1, r1, x2, y2, r2):
                    dsu.union(i, j)

            if inter_circle_seg(x1, y1, r1, 0, 0, 0, Y):
                dsu.union(i, N)
            if inter_circle_seg(x1, y1, r1, 0, Y, X, Y):
                dsu.union(i, N)
            if inter_circle_seg(x1, y1, r1, 0, 0, X, 0):
                dsu.union(i, N + 1)
            if inter_circle_seg(x1, y1, r1, X, 0, X, Y):
                dsu.union(i, N + 1)

        return dsu.find(N) != dsu.find(N + 1)


class DSU:
    def __init__(self, N):
        self.par = list(range(N))
        self.sz = [1] * N

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False
        if self.sz[xr] < self.sz[yr]:
            xr, yr = yr, xr
        self.par[yr] = xr
        self.sz[xr] += self.sz[yr]
        return True

    def size(self, x):
        return self.sz[self.find(x)]
17859