<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:
        circles = [tuple(c) for c in circles]
        circles.sort(key=lambda xyr: xyr[0] - xyr[2])
        neighbors = defaultdict(list)

        corners = [(0, 0), (xCorner, 0), (0, yCorner), (xCorner, yCorner)]

        working_set = []
        for c in circles:
            x, y, r = c
            
            in_corner = [(x - cx) ** 2 + (y - cy) ** 2 <=  r*r for cx, cy in corners]
            
            # side x = 0
            if r >= abs(x) and (0 <= y <= yCorner or in_corner[0] or in_corner[2]):
                neighbors[c].append(0)
            # side x = xCorner
            if r >= abs(x - xCorner) and (0 <= y <= yCorner or in_corner[1] or in_corner[3]):
                neighbors[c].append(1)
            # side y = 0
            if r >= abs(y) and (0 <= x <= xCorner or in_corner[0] or in_corner[1]):
                neighbors[c].append(2)
            # side y = yCorner
            if r >= abs(y - yCorner) and (0 <= x <= xCorner or in_corner[2] or in_corner[3]):
                neighbors[c].append(3)

            if not neighbors[c] and not (0 <= x <= xCorner and 0 <= y <= yCorner):
                continue

            for _, c1 in working_set:
                x1, y1, r1 = c1
                
                d2 = (x - x1) ** 2 + (y - y1) ** 2
                if (r + r1) ** 2 < d2:
                    continue

                # handle easy case, where a point is in the rectangle
                point_in_rectangle = (
                    (0 <= x <= xCorner and 0 <= y <= yCorner)
                    or (0 <= x1 <= xCorner and 0 <= y1 <= yCorner)
                )
                # handle hard case, where both points are out of the rectangle
                line_in_rectangle = False
                if not point_in_rectangle:
                    dx = x1 - x
                    dy = y1 - y
                    for (q1, q2), (s1, s2) in [
                        ((0, 0), (0, yCorner)),
                        ((0, 0), (xCorner, 0)),
                        ((0, yCorner), (xCorner, 0)),
                        ((xCorner, 0), (0, yCorner)),
                    ]:
                        # test for colinear / parallel.
                        rxs = cross(dx, dy, s1, s2)
                        if rxs == 0:
                            continue
                        # print(cross(q1 - x, q2 - y, s1, s2) / rxs, cross(q1 - x, q2 - y, dx, dy) / rxs)
                        if (
                            0 <= cross(q1 - x, q2 - y, s1, s2) / rxs <= 1
                            and 0 <= cross(q1 - x, q2 - y, dx, dy) / rxs <= 1
                        ):
                            line_in_rectangle = True
                            break
                
                # print(point_in_rectangle, line_in_rectangle)
                if point_in_rectangle or line_in_rectangle:
                    neighbors[c].append(c1)

            heappush(working_set, (x + r, c))
            while working_set[0][0] < x - r:
                heappop(working_set)
            for n in neighbors[c]:
                if n != c:
                    neighbors[n].append(c)

        visited = set()
        for x in [0, 3]:
            if x in visited:
                continue
            to_visit = [x]
            visited.add(x)
            while to_visit:
                x = to_visit.pop()
                for n in neighbors[x]:
                    if n not in visited:
                        to_visit.append(n)
                        visited.add(n)
                        if n == 1 or n == 2:
                            return False
        return True

def cross(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1
21484