<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
from collections import deque, defaultdict
from typing import List

class Solution:
    def canReachCorner(self, X: int, Y: int, p: List[List[int]]) -> bool:
        circles = []
        for arr in p:
            if arr not in circles:
                circles.append(arr)
        
        def circles_intersect(c1, c2):
            x1, y1, r1 = c1
            x2, y2, r2 = c2
            distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
            return distance <= r1 + r2
        
        adj = defaultdict(list)

        for i in range(len(circles)):
            for j in range(i + 1, len(circles)):
                if circles_intersect(circles[i], circles[j]):
                    adj[tuple(circles[i])].append(circles[j])
                    adj[tuple(circles[j])].append(circles[i])

        # Left touch Down
        visited = set()
        queue = deque([])

        for x, y, r in circles:
            y_val_pos = math.sqrt(r ** 2 - x ** 2) + y if r ** 2 - x ** 2 >= 0 else -1e9
            y_val_neg = -math.sqrt(r ** 2 - x ** 2) + y if r ** 2 - x ** 2 >= 0 else -1e9
            if (y_val_pos >= 0 and y_val_neg <= Y): # Two intersections
                queue.append((x, y, r))
                visited.add((x, y, r))
            elif y_val_pos == y_val_neg and 0 <= y_val_pos <= Y:
                queue.append((x, y, r))
                visited.add((x, y, r))

        while queue:
            x, y, r = queue.popleft()
            x_val_pos = math.sqrt(r ** 2 - y ** 2) + x if r ** 2 - y ** 2 >= 0 else -1e9
            x_val_neg = -math.sqrt(r ** 2 - y ** 2) + x if r ** 2 - y ** 2 >= 0 else -1e9
            if (x_val_neg <= X and x_val_pos >= 0) and y-r <= 0 <= y+r:
                return False
            elif x_val_neg == x_val_pos and 0 <= x_val_pos <= X and y-r <= 0 <= y+r:
                return False
            
            for nei in adj[(x, y, r)]:  
                if tuple(nei) not in visited:
                    visited.add(tuple(nei))
                    queue.append(nei)

        # Left touch right
        visited = set()
        queue = deque([])

        for x, y, r in circles:
            y_val_pos = math.sqrt(r ** 2 - x ** 2) + y if r ** 2 - x ** 2 >= 0 else -1e9
            y_val_neg = -math.sqrt(r ** 2 - x ** 2) + y if r ** 2 - x ** 2 >= 0 else -1e9
            if (y_val_pos >= 0 and y_val_neg <= Y): # Two intersections
                queue.append((x, y, r))
                visited.add((x, y, r))
            elif y_val_pos == y_val_neg and 0 <= y_val_pos <= Y:
                queue.append((x, y, r))
                visited.add((x, y, r))

        while queue:
            x, y, r = queue.popleft()
            y_val_pos = math.sqrt(r ** 2 - (X-x) ** 2) + y if r ** 2 - (X-x) ** 2 >= 0 else -1e9
            y_val_neg = -math.sqrt(r ** 2 - (X-x) ** 2) + y if r ** 2 - (X-x) ** 2 >= 0 else -1e9
            if (y_val_neg <= Y and y_val_pos >= 0) and x-r <= X <= x+r:
                return False
            elif y_val_neg == y_val_pos and 0 <= y_val_pos <= Y and x-r <= X <= x+r:
                return False
            
            for nei in adj[(x, y, r)]:  
                if tuple(nei) not in visited:
                    visited.add(tuple(nei))
                    queue.append(nei)
        
        
        # Right touch Top
        visited = set()
        queue = deque([])

        for x, y, r in circles:
            y_val_pos = math.sqrt(r ** 2 - (X-x) ** 2) + y if r ** 2 - (X-x) ** 2 >= 0 else -1e9
            y_val_neg = -math.sqrt(r ** 2 - (X-x) ** 2) + y if r ** 2 - (X-x) ** 2 >= 0 else -1e9
            if (y_val_pos >= 0 and y_val_neg <= Y): # Two intersections
                queue.append((x, y, r))
                visited.add((x, y, r))
            elif y_val_pos == y_val_neg and 0 <= y_val_pos <= Y:
                queue.append((x, y, r))
                visited.add((x, y, r))
        
        while queue:
            x, y, r = queue.popleft()
            x_val_pos = math.sqrt(r ** 2 - (Y-y) ** 2) + x if r ** 2 - (Y-y) ** 2 >= 0 else -1e9
            x_val_neg = -math.sqrt(r ** 2 - (Y-y) ** 2) + x if r ** 2 - (Y-y) ** 2 >= 0 else -1e9
            if (x_val_neg <= X and x_val_pos >= 0) and y-r <= Y <= y+r:
                return False
            elif x_val_neg == x_val_pos and 0 <= x_val_pos <= X and y-r <= Y <= y+r:
                return False
            
            for nei in adj[(x, y, r)]:  
                if tuple(nei) not in visited:
                    visited.add(tuple(nei))
                    queue.append(nei)
        
        # Top touch down
        visited = set()
        queue = deque([])

        for x, y, r in circles:
            x_val_pos = math.sqrt(r ** 2 - (Y-y) ** 2) + x if r ** 2 - (Y-y) ** 2 >= 0 else -1e9
            x_val_neg = -math.sqrt(r ** 2 - (Y-y) ** 2) + x if r ** 2 - (Y-y) ** 2 >= 0 else -1e9
            if (x_val_neg <= X and x_val_pos >= 0):
                queue.append((x, y, r))
                visited.add((x, y, r))
            elif x_val_neg == x_val_pos and 0 <= x_val_pos <= X:
                queue.append((x, y, r))
                visited.add((x, y, r))
        
        while queue:
            x, y, r = queue.popleft()
            x_val_pos = math.sqrt(r ** 2 - y ** 2) + x if r ** 2 - y ** 2 >= 0 else -1e9
            x_val_neg = -math.sqrt(r ** 2 - y ** 2) + x if r ** 2 - y ** 2 >= 0 else -1e9
            print(x,y,r, x_val_pos, x_val_neg)
            if (x_val_neg <= X and x_val_pos >= 0) and y-r <= 0 <= y+r:
                return False
            elif x_val_neg == x_val_pos and 0 <= x_val_pos <= X and y-r <= 0 <= y+r:
                return False
            
            for nei in adj[(x, y, r)]:  
                if tuple(nei) not in visited:
                    visited.add(tuple(nei))
                    queue.append(nei)





        return True

23296