<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>

"""
Explanation:
even if two circles that intersect, cover opposite corners, 
there might still be a valid path. 
That is the trickiest edge case, and their two intersections are actually completely out of the rectangle.
First I thought maybe to check if their intersection points are inside the rectangle,
but that won't work for all cases.
So a better approach is to check if the line between their two intersection points,
intersects with any of the four rectangle sides. 
or if the intersections points lie inside the rectangle.



"""
from typing import List



import math

# Function to check if two circles touch each other
def intersect(x1, y1, x2, y2, r1, r2):
    d = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
    t = find_intersection(x1,y1,r1,x2,y2,r2)

    if(d <= r1 - r2):
        return True
    elif(d <= r2 - r1):
        return True
    elif(d < r1 + r2):
        return True
    elif(d == r1 + r2):
        return True
    else:
        return False


def find_intersection(x1, y1, r1, x2, y2, r2):
    # Calculate the distance between the centers
    d = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

    # Check if circles intersect
    if d > r1 + r2 or d < abs(r1 - r2) or d == 0:
        return None  # No intersection or the circles are coincident

    # Calculate the point P2 where the line through the circle intersection points crosses the line between the circle centers
    a = (r1 ** 2 - r2 ** 2 + d ** 2) / (2 * d)
    h = math.sqrt(r1 ** 2 - a ** 2)

    # Coordinates of point P2
    x3 = x1 + a * (x2 - x1) / d
    y3 = y1 + a * (y2 - y1) / d

    # Calculate the intersection points
    intersection1 = (x3 + h * (y2 - y1) / d, y3 - h * (x2 - x1) / d)
    intersection2 = (x3 - h * (y2 - y1) / d, y3 + h * (x2 - x1) / d)

    return intersection1, intersection2
def check_point_inside(x,y,r,X,Y):
    if x > 0 and y > 0 and x < X and y < Y:
        return True

    return False
def distance(x,y,i,j,r):
    return  (x-i)*(x-i) + (y-j)*(y-j) <=r*r


def orientation(p, q, r):
    """
    Find the orientation of the ordered triplet (p, q, r).
    0 -> p, q and r are collinear
    1 -> Clockwise
    2 -> Counterclockwise
    """
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    elif val > 0:
        return 1
    else:
        return 2


def on_segment(p, q, r):
    """
    Check if point q lies on line segment 'pr' when p, q, r are collinear.
    """
    if min(p[0], r[0]) <= q[0] <= max(p[0], r[0]) and min(p[1], r[1]) <= q[1] <= max(p[1], r[1]):
        return True
    return False

def deni_function(x1, y1, x2, y2, r1, r2, X,Y):
    t = find_intersection(x1,y1,r1,x2,y2,r2)
    if t == None:
        return False
    if t[0][0]>=0 and t[0][0]<=X and t[0][1]>=0 and t[0][1]<=Y:
        return True
    if t[1][0] >= 0 and t[1][0] <= X and t[1][1] >= 0 and t[1][1] <= Y:
        return True

    p1 = t[0]
    q1 = t[1]

    p2 = (0,0)
    q2 = (X,0)

    if do_intersect(p1,q1,p2,q2):
        return True

    p2 = (0, 0)
    q2 = (0, Y)

    if do_intersect(p1, q1, p2, q2):
        return True

    p2 = (X,Y)
    q2 = (X, 0)

    if do_intersect(p1, q1, p2, q2):
        return True

    p2 = (X,Y)
    q2 = (0, Y)

    if do_intersect(p1, q1, p2, q2):
        return True

    return False
def do_intersect(p1, q1, p2, q2):


    """
    Check if line segment 'p1q1' and 'p2q2' intersect.
    """
    # Find the four orientations needed for the general and special cases
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # General case
    if o1 != o2 and o3 != o4:
        return True

    # Special cases
    # p1, q1 and p2 are collinear and p2 lies on segment p1q1
    if o1 == 0 and on_segment(p1, p2, q1):
        return True

    # p1, q1 and q2 are collinear and q2 lies on segment p1q1
    if o2 == 0 and on_segment(p1, q2, q1):
        return True

    # p2, q2 and p1 are collinear and p1 lies on segment p2q2
    if o3 == 0 and on_segment(p2, p1, q2):
        return True

    # p2, q2 and q1 are collinear and q1 lies on segment p2q2
    if o4 == 0 and on_segment(p2, q1, q2):
        return True

    # If none of the cases hold, the segments don't intersect
    return False


import collections
class Solution:
    def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool:
        a = circles

        up = [False for i in a]
        down = [False for i in a]
        left = [False for i in a]
        right = [False for i in a]
        parent = [i for i in range(len(a))]
        processed = [False for i in a]
        q = collections.deque()

        for i in range(len(a)):
            x,y,r = a[i]
            if x >= 0 and y >= 0 and x <= X and y <= Y:
                if x+r>=X:
                    right[i]=True
                if x-r<=0:
                    left[i]=True
                if y+r>=Y:
                    up[i]=True
                if y-r<=0:
                    down[i]=True

                if up[i] or down[i] or left[i] or right[i]:
                    q.append(i)
            else:
                # either a point from inside next to corner, is inside the circle
                # or left most point of circle is inside rectangle
                if check_point_inside(x-r,y,r,X,Y):
                    right[i]=True
                if check_point_inside(x+r,y,r,X,Y):
                    left[i]=True
                if check_point_inside(x,y-r,r,X,Y):
                    up[i]=True
                if check_point_inside(x,y+r,r,X,Y):
                    down[i]=True

                x2 = 0.01
                y2 = 0.01
                if distance(x2,y2,x,y,r):
                    left[i] = True
                    down[i]=True
                x2 = 0.01
                y2 = Y-0.01
                if distance(x2,y2,x,y,r):
                    left[i] = True
                    up[i]=True
                x2 = X-0.01
                y2 = 0.01
                if distance(x2,y2,x,y,r):
                    right[i] = True
                    down[i]=True
                x2 = X-0.01
                y2 = Y-0.01
                if distance(x2,y2,x,y,r):
                    right[i] = True
                    up[i]=True

                if up[i] or down[i] or left[i] or right[i]:
                    q.append(i)

        if len(q)==0:
            return True

        while len(q)>0:
            current_index = q[0]
            if processed[current_index]:
                q.popleft()
                continue
            processed[current_index]=True
            x,y,r = a[q[0]]
            q.popleft()
            parent_of_this = current_index
            while parent_of_this!=parent[parent_of_this]:
                parent_of_this = parent[parent_of_this]
            for i in range(len(a)):
                if processed[i]==False:
                    x2,y2,r2 = a[i]
                    if intersect(x,y,x2,y2,r,r2) and deni_function(x,y,x2,y2,r,r2,X,Y):
                        parenti = i
                        while parenti != parent[parenti]:
                            parenti = parent[parenti]



                        f = parent_of_this
                        g = parenti
                        up[f]|=up[g]
                        down[f]|=down[g]
                        left[f]|=left[g]
                        right[f]|=right[g]

                        parent[parenti]=parent_of_this

                        q.append(i)

        for i in range(len(a)):
            if up[i] and down[i]:
                return False
            if left[i] and right[i]:
                return False
            if up[i] and right[i]:
                return False
            if down[i] and left[i]:
                return False

        return True





34171