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

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