<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:
        """
        n <= 1000
        
        從範例二可以做一個快速檢查，如果起點(0,0)被任何一個圓覆蓋，則必然寸步難行。
        同理終點也一樣。
        
        既然起點可以出發，那我們可以假設從x方向檢查，如果我派一萬隻機器人去走，如果無法通過x方向，則必然有一道圍牆阻隔。
                
        我們可以分別從x方向和y方向檢查，是否有機會穿越
        也就是說，n個圓對n個圓，是否重疊/相切
        這些相切的圓，是否會構成城牆
        """
        def sol1():
            n = len(circles)

            def is_circle_touch_circle(c1, c2):
                x1, y1, r1 = c1
                x2, y2, r2 = c2
                return (x1-x2)**2 + (y1-y2)**2 <= (r1+r2)**2
            
            def is_circles_touch_one_point(circles, x, y):         
                for c in circles:
                    if is_circle_touch_circle(c, (x, y, 0)):
                        return True
                    return False
                
            if is_circles_touch_one_point(circles, 0, 0): return False
            if is_circles_touch_one_point(circles, X, Y): return False
            
            
            """
            把多個圓形交集，是否會在x方向製造一堵"長城"
                  Y1
                ______
                |  x  |
                | xxx |
            X0  |  x  |  X1
                |___x_|
            
                  Y0
            
            需檢查
            X0 - X1 構成城牆
            Y0 - Y1
            
            此外，城牆也可能是扇形
            ______
            |    |
            |xx  |
            |  x |
            |__x_|
            
            故要檢查
            X0 - Y0
            X1 - Y1
            
        
            """             
            def build_graph(circles):   # O(n^2)
                n = len(circles)
                adj = defaultdict(list)
                for i in range(n):
                    for j in range(n):
                        if i == j:
                            continue
                        if is_circle_touch_circle(circles[i], circles[j]):
                            adj[i].append(j)
                            adj[j].append(i)           
                return adj
            
            def find_circles_touch_axis(circles, axis, val):
                ret = []
                for i in range(n):
                    cx, cy, r = circles[i]
                    if axis == 'x' and abs(cx - val) <= r:
                        ret.append(i)
                    elif axis == 'y' and abs(cy - val) <= r:
                        ret.append(i)

                return set(ret)
            
            def can_connect_groups(graph, g1, g2):  # O(n)
                if not g1 or not g2:
                    return False
                
                visited = set()
                que = deque()
                for i in g1:
                    que.append(i)
                
                while que:
                    i = que.popleft()
                    if i in visited:
                        continue
                    visited.add(i)
                    
                    if i in g2:
                        return True
                    
                    for nxt in graph[i]:
                        que.append(nxt)
                
                return False
            
            
            graph = build_graph(circles)
            
            X0 = find_circles_touch_axis(circles, 'x', 0)
            X1 = find_circles_touch_axis(circles, 'x', X)
            Y0 = find_circles_touch_axis(circles, 'y', 0)
            Y1 = find_circles_touch_axis(circles, 'y', Y)
                
            if can_connect_groups(graph, X0, X1): return False
            if can_connect_groups(graph, Y0, Y1): return False
            if can_connect_groups(graph, X0, Y0): return False
            if can_connect_groups(graph, X1, Y1): return False
            
            return True
        
        return sol1()
        """
        總複雜度：
        build_graph: O(n^2)
        find_circles_touch_axis: O(n)
        
        can_build_wall_from_two_group: O(n)
        總複雜度最高也只有O(n^2)        
        """
        
52296