<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:
        def intersect(circle1, circle2):
            x0, y0, r0 = circle1
            x1, y1, r1 = circle2
            d=math.sqrt((x1-x0)**2 + (y1-y0)**2)
            if d > r0 + r1 or d < abs(r0-r1) or (d == 0 and r0 == r1):
                return False
            a=(r0**2-r1**2+d**2)/(2*d)
            h=math.sqrt(r0**2-a**2)
            x2=x0+a*(x1-x0)/d   
            y2=y0+a*(y1-y0)/d   
            x3=x2+h*(y1-y0)/d     
            y3=y2-h*(x1-x0)/d
            x4=x2-h*(y1-y0)/d
            y4=y2+h*(x1-x0)/d
            return 0 <= x3 <= X and 0 <= x4 <= X and 0 <= y3 <= Y and 0 <= y4 <= Y
        
        '''def intersecty(circle, x2):
            x, y, r = circle
            if not x - r <= x2 <= x + r:
                return False
            vert = (r ** 2 - (x - x2) ** 2)
            print(vert)
            return (y - Y) ** 2 <= vert <= y ** 2 or y ** 2 <= vert <= (Y - y) ** 2
        '''
        def intersectX(circle, y2):
            x, y, r = circle
            if not (y - r <= y2 <= y + r):
                return False
            dy2 = (y - y2) ** 2
            if dy2 > r ** 2:
                return False
            dx = sqrt(r ** 2 - dy2)
            x_min, x_max = x - dx, x + dx
            return x_min <= X and x_max >= 0

        def intersecty(circle, x2):
            x, y, r = circle
            if not (x - r <= x2 <= x + r):
                return False
            dx2 = (x - x2) ** 2
            if dx2 > r ** 2:
                return False
            dy = sqrt(r ** 2 - dx2)
            y_min, y_max = y - dy, y + dy
            return y_min <= Y and y_max >= 0

        n = len(circles)
        g = defaultdict(list)
        q = deque()
        for i in range(n):
            for j in range(i):
                if intersect(circles[i], circles[j]):
                    g[i].append(j)
                    g[j].append(i)
            if intersecty(circles[i], 0) or intersectX(circles[i], Y):
                q.append(i)

        visited = set()
        while q:
            cur = q.popleft()
            if cur in visited:
                continue
            if intersecty(circles[cur], X) or intersectX(circles[cur], 0):
                return False
            visited.add(cur)
            for j in g[cur]:
                q.append(j)
        return True
42328