<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:
        circles = [circle for circle in circles if self.isCircleInRectangle(circle, X, Y) ]
        edges = {}
        touchedEdges = {0:set(), 1:set()}
        for index, circle in enumerate(circles):
            circlesTouchedEdges = self.getTouchingEdges(circle, X, Y)
            for edge in circlesTouchedEdges:
                touchedEdges[edge].add(index)
            edges[index] = set()
            for index2, circle2 in enumerate(circles):
                if index!=index2 and self.isDistanceLessThanEqualTo(circle[0], circle[1], circle2[0], circle2[1], circle[2]+circle2[2]) and ((circle[0]+circle2[0])/2<X or (circle[1]+circle2[1])/2<Y):
                    edges[index].add(index2)
        q = list(touchedEdges[0])
        pointer = 0
        while pointer<len(q):
            pointed = q[pointer]
            q+=list(edges[pointed]-touchedEdges[0])
            touchedEdges[0]|=edges[pointed]
            if touchedEdges[0]&touchedEdges[1]:
                return False
            pointer+=1
        return True
    
    def getTouchingEdges(self, circle, X, Y) -> Set[int]:
        ans = set()
        x, y, rad = circle
        if x-rad<=0:
            if y<=Y or self.isDistanceLessThanEqualTo(x,y,0,Y,rad):
                ans.add(0)
        if y+rad>=Y:
            if x<=X or self.isDistanceLessThanEqualTo(x,y,X,Y,rad):
                ans.add(0)
        if x+rad>=X:
            if y<=Y or self.isDistanceLessThanEqualTo(x,y,X,Y,rad):
                ans.add(1)
        if y-rad<=0:
            if y<=Y or self.isDistanceLessThanEqualTo(x,y,X,0,rad):
                ans.add(1)
        return ans
    
    def isCircleInRectangle(self, circle, X, Y) -> bool:
        return (circle[0]-circle[2]<X and circle[1]-circle[2]<Y) or self.isDistanceLessThanEqualTo(circle[0], circle[1], X, Y, circle[2])
    
    def isDistanceLessThanEqualTo(self, x1, y1, x2, y2, dis) -> bool:
        return (x1-x2)**2+(y1-y2)**2<=dis**2
70421