<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 UF:
    def __init__(self, n):
        self.n=n
        self.p=[i for i in range(n)]
        self.conditions = []
        self.h = [0 for _ in range(n)]

    def find(self, i):
        if self.p[i]==i:
            return i
        self.p[i] = self.find(self.p[i])
        return self.p[i]
    
    def union(self, i,j):
        pi=self.find(i)
        pj=self.find(j)
        if pi==pj:
            return

        if self.h[pi]>=self.h[pj]:
            if self.h[pi]==self.h[pj]:
                self.h[pi]+=1
            self.p[pj] = pi
            self.conditions[pi] = [
                self.conditions[pi][0] or self.conditions[pj][0] or self.conditions[i][0] or self.conditions[j][0],
                self.conditions[pi][1] or self.conditions[pj][1] or self.conditions[i][1] or self.conditions[j][1],
                self.conditions[pi][2] or self.conditions[pj][2] or self.conditions[i][2] or self.conditions[j][2],
                self.conditions[pi][3] or self.conditions[pj][3] or self.conditions[i][3] or self.conditions[j][3],
            ]
        else:
            self.p[pi] = pj
            self.conditions[pj] = [
                self.conditions[pi][0] or self.conditions[pj][0] or self.conditions[i][0] or self.conditions[j][0],
                self.conditions[pi][1] or self.conditions[pj][1] or self.conditions[i][1] or self.conditions[j][1],
                self.conditions[pi][2] or self.conditions[pj][2] or self.conditions[i][2] or self.conditions[j][2],
                self.conditions[pi][3] or self.conditions[pj][3] or self.conditions[i][3] or self.conditions[j][3],
            ]



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

        bold assumption:
        if exist a connected componet which touches (y=0 and x=0) or (y=Y and x=X),
            =>blocked diagonally=>not possible
        else possible


        """
        n=len(circles)
        #adj = defaultdict(list) #adj among of circles
        edges=[]
        for j in range(n):
            xj,yj,rj = circles[j]
            for i in range(j+1, n):
                xi,yi,ri = circles[i]
                centerDis= (xi-xj)**2 + (yi-yj)**2
                radSum= (ri+rj)**2
                if centerDis<=radSum:#overlap
                    # adj[i].append(j)
                    # adj[j].append(i)
                    edges.append((i,j))
        
        uf = UF(n)
        for i,c in enumerate(circles):#check all 4 borders if overlap with circle
            x,y,r = c
            this=[False, False, False, False]
            #x=0
            if r>=x-0:
                this[0]=True
            #y=0
            if r>=y-0:
                this[1]=True
            #x=X
            if abs(x-X)<=r:
                this[2]=True
            #y=Y
            if abs(y-Y)<=r:
                this[3]=True
            uf.conditions.append(this)

        #union
        for a,b in edges:
            uf.union(a,b)
        """
        if exist a connected componet which touches (y=0 and x=0) or (y=Y and x=X)
                            or (y=0 and y=Y) or (x=0 and x=X)
            =>blocked diagonally=>not possible
        """
        for i in range(n):
            this = uf.conditions[uf.find(i)]
            if ((this[0] and this[1]) or (this[2] and this[3]) 
                or (this[0] and this[2]) or (this[1] and this[3])):
                return False
        
        return True

            

            




66796