<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>

import math
class Solution:
    def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool:
        left = set()
        right = set()
        up = set()
        down = set()
        def point_in_circle(h, k, r, x, y):
            distance = math.sqrt((x - h)**2 + (y - k)**2)
            if distance <= r:
                return True
            else:
                return False
        

        def vertical_line_intersection(h, k, r, x_k):
            a = x_k - h
            if r**2 < a**2:
                return []
            
            y1 = k + math.sqrt(r**2 - a**2)
            y2 = k - math.sqrt(r**2 - a**2)
            
            return (x_k, y1), (x_k, y2)
        def circles_intersect(i, j):
            h1, k1, r1 = circles[i]
            h2, k2, r2 = circles[j]
            distance_centers = math.sqrt((h2 - h1)**2 + (k2 - k1)**2)
            
            if distance_centers > r1 + r2:
                return False  
            elif distance_centers < abs(r1 - r2):
                return False 
            else:
                return True 
        def find_intersections(h, k, r, m, c):
            A = 1 + m**2
            B = 2 * (m * (c - k) - h)
            C = h**2 + (c - k)**2 - r**2

            discriminant = B**2 - 4 * A * C

            if discriminant < 0:
                return []
            elif discriminant == 0:
                x = -B / (2 * A)
                y = m * x + c
                return [(x, y)]
            else:
                sqrt_discriminant = math.sqrt(discriminant)
                x1 = (-B + sqrt_discriminant) / (2 * A)
                x2 = (-B - sqrt_discriminant) / (2 * A)
                y1 = m * x1 + c
                y2 = m * x2 + c
                return [(x1, y1), (x2, y2)]
            
        for i in range(len(circles)):
            h,k,r = circles[i]
            if point_in_circle(h,k,r, 0, 0) or point_in_circle(h,k,r, X,Y):
                return False
            #left
            m = float('inf')
            c = 0
            res = vertical_line_intersection(h,k,r,c)
            for x1,y1 in res:
                if y1 == 0: return False
                if 0 <= y1 <= Y:
                    left.add(i)

            #right
            m = float('inf')
            c = X
            res = vertical_line_intersection(h,k,r,c)
            for x1,y1 in res:
                if y1 == Y: return False
                if 0 <= y1 <= Y:
                    right.add(i)

            #down
            m = 0
            c = 0
            res = find_intersections(h,k,r,m,c)
            for x1,y1 in res:
                if x1 == 0: return False
                if 0 <= x1 <= X:
                    down.add(i)
            
            #up
            m = 0
            c = Y
            res = find_intersections(h,k,r,m,c)
            for x1,y1 in res:
                if x1 == X: return False
                if 0 <= x1 <= X:
                    up.add(i)

        adj = defaultdict(list)
        for i in range(len(circles)):
            for j in range(i+1, len(circles)):
                if circles_intersect(i, j):
                    adj[i].append(j)
                    adj[j].append(i)
        
        def dfs(i):
            if i in vis:
                return False
            vis.add(i)
            if i in right or i in down:
                return True
            for nei in adj[i]:
                if dfs(nei):
                    return True
            return False
        for i in left:
            vis = set()
            if dfs(i):
                return False
        for i in up:
            vis = set()
            if dfs(i):
                return False
        return True
            



71328