<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, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:


        # for each circle get the list of edges it is touching or inside it
        # for each pair of circle get the different set of circles touching each other
        # for each set of touching circles check the list of involved edges
        #   based on the list of edges involved in this set check if can reach corner
        tlc = [0,yCorner]   # top_left_corner
        trc = [xCorner, yCorner]    # top_right_corner
        blc = [0, 0]    # bottom_left_corner
        brc = [xCorner, 0]  # bottom_right_corner
        
        def get_dist(p1, p2):
            x1, y1 = p1
            x2, y2 = p2
            
            return ((y2-y1)**2 + (x2-x1)**2) ** (1/2)
        
        
        ce_list = []
        # for each circle get the list of edges it is touching or inside it
        for circle in circles:
            cx, cy, cr = circle
            crossing_edges = [False, False, False, False]  # left, right, up, down
            if cx <= xCorner and cy <= yCorner:  # Inside rectangle
                if cx-cr <= 0:
                    crossing_edges[0] = True  # left
                if cx+cr >= xCorner:
                    crossing_edges[1] = True  # right
                if cy+cr >= yCorner:
                    crossing_edges[2] = True  # up
                if cy-cr <= 0:
                    crossing_edges[3] = True  # down
                    
            if cx <= xCorner and cy > yCorner:  # Above rectangle
                if cy-cr < yCorner:
                    crossing_edges[2] = True  # Up
                if cy-cr <= 0:
                    crossing_edges[3] = True  # Down
                if get_dist((cx, cy), tlc) < cr:
                    crossing_edges[0] = True  # left
                if get_dist((cx, cy), trc) < cr:
                    crossing_edges[1] = True  # right

            if cx > xCorner and cy <= yCorner:  # Beside rectangle
                if cx-cr < xCorner:
                    crossing_edges[1] = True  # right
                if cx-cr <= 0:
                    crossing_edges[0] = True  # left
                if get_dist((cx, cy), trc) < cr:
                    crossing_edges[2] = True  # Up
                if get_dist((cx, cy), brc) < cr:
                    crossing_edges[3] = True  # Down
            
            if cx > xCorner and cy > yCorner:  # Diagonaly above rectangle                
                if get_dist((cx, cy), trc) < cr:
                    crossing_edges[2] = True  # Up
                    crossing_edges[1] = True  # right
                if get_dist((cx, cy), brc) < cr:
                    crossing_edges[3] = True  # Down
                if get_dist((cx, cy), tlc) < cr:
                    crossing_edges[0] = True  # left
                    
            ce_list.append(crossing_edges)     
                
        print("#ce_list; ", ce_list)
        
        # for each pair of circle get the different set of circles touching each other
        cc_list = [[] for i in range(len(circles))]
        for i in range(len(circles)):
            x1, y1, r1 = circles[i]
            is_i_inside = x1<xCorner and y1<yCorner
            for j in range(len(circles)):
                if i == j:
                    continue
                x2, y2, r2 = circles[j]
                is_j_inside = x2<xCorner and y2<yCorner
                
                # if not is_i_inside and not is_j_inside:
                #     continue
                
                cdist = get_dist((x1, y1), (x2, y2))
                
                if cdist <= (r1+r2):
                    if not is_i_inside and not is_j_inside:
                        xmid, ymid = (x1+x2)/2, (y1+y2)/2
                        if xmid>=xCorner and ymid>=yCorner:
                            continue
                    cc_list[i].append(j)
                    
        # print("## cc_list: ", cc_list)
                    
        # Get the groups of circles touching each other using above connection list
        circle_groups = []
        visited = [False] * len(circles)
        
        #     if current circle is not visited, 
        #         then initialize new group with current circle        
        #         iterate over all the connections and their connections and add them to group if not already visited
        # for each circle connections
        for i, cc in enumerate(cc_list):
            # check if current circle is not visited, 
            # print("@ visited ", visited)
            if not visited[i]:
                new_group = [i]
                visited[i] = True
                idx = 0
                gqueue = cc
                
                while idx < len(gqueue):                                       
                    glen = len(gqueue)
                    for j in range(idx, glen):
                        # print("@j ", j)
                        cle = gqueue[j]
                        if not visited[cle]:
                            visited[cle] = True
                            new_group.append(cle)
                            gqueue.extend(cc_list[cle])
                            
                    idx = glen
                
                # print("@@ ", i, new_group)
                    
                circle_groups.append(new_group)               
        print("### circle_groups", circle_groups)
        
        # for each set of touching circles check the list of involved edges
        
        for group in circle_groups:
            tedges = [False, False, False, False]  # left, right, up, down
            for cc in group:
                tedges = [x or y for x, y in zip(tedges, ce_list[cc])]
            
            # based on the list of edges involved in this set check if can reach corner
            if tedges[0] and tedges[1]:  # touching Left and Right
                print("touching Left and Right", group)
                return False
            
            if tedges[0] and tedges[3]:  # touching Left and Down
                print("touching Left and Down", group)
                return False
                
            if tedges[1] and tedges[2]:  # touching Right and Up
                print("touching Right and Up", group)
                return False
            
            if tedges[2] and tedges[3]:  # touching Up and Down
                print("touching Up and Down", group)
                return False
        
        return True


        
57734