<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 DSU:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    # returns 1 if two components joined, 0 if same component
    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx == rooty:
            return 0
        
        if self.rank[rootx] > self.rank[rooty]:
            self.rank[rootx] += self.rank[rooty]
            self.parent[rooty] = rootx
        else:
            self.rank[rooty] += self.rank[rootx]
            self.parent[rootx] = rooty
        self.n -= 1
        return 1


class Solution:
    def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool:
        def circleFullyWithinRectangle(x, y, r):
            return x - r > 0 and x + r < X and y - r > 0 and y + r < Y
        def getCircleBadTypes(x, y, r):
            badTypes = set()
            if x - r <= 0:
                badTypes.add("left")
            if x + r >= X:
                badTypes.add("right")
            if y - r <= 0:
                badTypes.add("bottom")
            if y + r >= Y:
                badTypes.add("top")
            return badTypes
        def circlesIntersect(circle1, circle2):
            # or are tangent
            x1, y1, r1 = circle1
            x2, y2, r2 = circle2
            return (x2 - x1) ** 2 + (y2 - y1) ** 2 <= (r1 + r2) ** 2

        neighbours = [[] for i in range(len(circles))]
        circleDSU = DSU(len(circles))
        for i in range(len(circles)):
            for j in range(len(circles)):
                if i == j:
                    continue
                if circlesIntersect(circles[i], circles[j]):
                    neighbours[i].append(j)
                    neighbours[j].append(i)
                    circleDSU.union(i + 1, j + 1) # 1-indexed because of my DSU implementation

        groupToBadTypes = dict()    
        for i in range(1, len(circles) + 1):
            par = circleDSU.find(i)
            if par not in groupToBadTypes:
                groupToBadTypes[par] = set()
            
            x, y, r = circles[i - 1]
            badTypes = getCircleBadTypes(x, y, r)
            groupToBadTypes[par] = groupToBadTypes[par].union(badTypes)

        # print(f"groupToBadTypes: {groupToBadTypes}")

        for par in groupToBadTypes:
            badTypes = groupToBadTypes[par]
            if "bottom" in badTypes and "top" in badTypes:
                return False
            if "left" in badTypes and "right" in badTypes:
                return False
            if "bottom" in badTypes and "left" in badTypes:
                return False
            if "top" in badTypes and "right" in badTypes:
                return False
        return True

        


        
        
53203