<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(object):
    def canReachCorner(self, X, Y, circles):
        """
        :type X: int
        :type Y: int
        :type circles: List[List[int]]
        :rtype: bool
        """

        # 排除無關圓
        # circles = [   
        #     circle for circle in circles if \
        #     self.center_out_rec(c, X, Y) and \
        #     not self.circle_intersec_up_edge(circle, X, Y) and \
        #     not self.circle_intersec_down_edge(circle, X, Y) and \
        #     not self.circle_intersec_right_edge(circle, X, Y) and \
        #     not self.circle_intersec_left_edge(circle, X, Y) \
        # ]

        # 建立graph
        graph = [[] for _ in range(len(circles)+2)]
        for i in range(len(circles)):
            for j in range(i+1, len(circles)):
                if self.circle_intersec_circle(circles[i], circles[j]):
                    graph[i].append(j)
                    graph[j].append(i)

        for j in range(len(circles)):
            if (
                self.circle_intersec_left_edge(circles[j], X, Y) or \
                self.circle_intersec_up_edge(circles[j], X, Y)
            ):
                graph[len(circles)].append(j)
                graph[j].append(len(circles))

        for j in range(len(circles)):
            if (
                self.circle_intersec_right_edge(circles[j], X, Y) or \
                self.circle_intersec_down_edge(circles[j], X, Y)
            ):
                graph[len(circles)+1].append(j)
                graph[j].append(len(circles)+1)

        return not self.search_path(graph, len(circles), len(circles)+1)

    def search_path(self, graph, start, goal):
        def dfs(current, goal, visited):
            if current == goal:
                return True
            visited.add(current)
            for neighbor in graph[current]:
                if neighbor not in visited:
                    if dfs(neighbor, goal, visited):
                        return True
            return False

        visited = set()
        return dfs(start, goal, visited)

    def center_out_rec(self, circle, X, Y):
        cx, cy, r = circle
        return (cx < -r or cx > X+r) or (cy < -r or cy > Y+r)
        
    def pt_in_circle(self, pt, circle):
        px, py = pt
        cx, cy, r = circle

        return (px-cx)**2 + (py-cy)**2 <= r**2

    def circle_intersec_circle(self, circle1, circle2):
        x1, y1, r1 = circle1
        x2, y2, r2 = circle2

        return (x1-x2)**2 + (y1-y2)**2 <= (r1+r2)**2

    def circle_intersec_right_edge(self, circle, X, Y):
        cx, cy, r = circle
        return ((X - r <= cx <= X + r) and (0 <= cy <= Y)) \
        or self.pt_in_circle((X, 0), circle) \
        or self.pt_in_circle((X, Y), circle)

    def circle_intersec_left_edge(self, circle, X, Y):
        cx, cy, r = circle
        return ((r >= cx >= -r) and (0 <= cy <= Y)) \
        or self.pt_in_circle((0, Y), circle) \
        or self.pt_in_circle((0, 0), circle)

    def circle_intersec_up_edge(self, circle, X, Y):
        cx, cy, r = circle
        return (Y - r <= cy <= Y + r) and (0 <= cx <= X) \
        or self.pt_in_circle((0, Y), circle) \
        or self.pt_in_circle((X, Y), circle)

    def circle_intersec_down_edge(self, circle, X, Y):
        cx, cy, r = circle
        return (r >= cy >= -r) and (0 <= cx <= X) \
        or self.pt_in_circle((X, 0), circle) \
        or self.pt_in_circle((0, 0), circle)

64078