<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:
        circles.sort()
        c2 = sorted([ (circles[i][0]-circles[i][2],i) for i in range(len(circles)) ])
        p = {}
        r = {}
        
        def find(i):
            x1,y1,r1 = circles[i]
            r.setdefault(i, {"mx" : x1 - r1, "max": x1 + r1, "my" : y1 - r1, "may": y1 + r1 })
            p.setdefault(i,i)
            if p[i] != i:
                p[i] = find(p[i])
            return p[i]
            
        for ti in range(len(c2)):
            i = c2[ti][-1]
        # for i in range(len(circles)):
            x1,y1,r1 = circles[i]
            stj = bisect_left(c2,(x1 - r1,i))
            etj = bisect_left(c2,(x1 + r1,i))
            for tj in range(stj,min(len(c2),etj+1)):
            # for j in range(i+1, len(circles)):
                # if j > i + 1: break
                j = c2[tj][-1]
                p1,p2 = find(i),find(j)
                
                x2,y2,r2 = circles[j]
                
                if p1 == p2:
                    r[p1]["mx"] = min(r[p1]["mx"],x1 - r1,x2 - r2)
                    r[p1]["max"] = max(r[p1]["max"],x1 + r1,x2 + r2)
                    
                    r[p1]["my"] = min(r[p1]["my"],y1 - r1,y2 - r2)
                    r[p1]["may"] = max(r[p1]["may"],y1 + r1,y2 + r2)
                    continue
                
                
                
                # d = math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
                # d = abs(x1 - x2)  + abs(y1 - y2)
                d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
                
                fl = d <= (abs(r1 - r2)) or d <= ((r1 + r2)) or (d <= ((r1 - r2)**2)) or (d <= (r1 + r2)**2) 
                

                # if (d <= r1 - r2) or (d <= r2 - r1) or (d < r1 + r2) or (d == r1 + r2) :
                if fl:
                    p1,p2 = find(i),find(j)
                    
                    if p1 != p2:
                        p[p2] = p1
                        r[p1]["mx"] = min(r[p1]["mx"],r[p2]["mx"])
                        r[p1]["max"] = max(r[p1]["max"],r[p2]["max"])

                        r[p1]["my"] = min(r[p1]["my"],r[p2]["my"])
                        r[p1]["may"] = max(r[p1]["may"],r[p2]["may"])
                    
                    # r.setdefault(p1, {"mx" : inf, "max": -inf, "my" : inf, "may": -inf })
                    r[p1]["mx"] = min(r[p1]["mx"],x1 - r1,x2 - r2)
                    r[p1]["max"] = max(r[p1]["max"],x1 + r1,x2 + r2)
                    
                    r[p1]["my"] = min(r[p1]["my"],y1 - r1,y2 - r2)
                    r[p1]["may"] = max(r[p1]["may"],y1 + r1,y2 + r2)
                    
                    if r[p1]["mx"] <= 0 and  r[p1]["my"] <= 0:
                        return False

                    if r[p1]["max"] >= X and  r[p1]["may"] >= Y:
                        return False

                    if r[p1]["mx"] <= 0 and  r[p1]["max"] >= X:
                        return False

                    if r[p1]["may"] >= Y and  r[p1]["my"] <= 0 :
                        return False
        
        # print(p)
        for i in range(len(circles)):
            p1 = find(i)
            x1,y1,r1 = circles[i]
            # r.setdefault(p1, {"mx" : x1 - r1, "max": x1 + r1, "my" : y1 - r1, "may": y1 + r1 })
            if p1 == i:
                # print(i,r)
                if r[p1]["mx"] <= 0 and  r[p1]["my"] <= 0:
                    return False
                
                if r[p1]["max"] >= X and  r[p1]["may"] >= Y:
                    return False
                
                if r[p1]["mx"] <= 0 and  r[p1]["max"] >= X:
                    return False
                
                if r[p1]["may"] >= Y and  r[p1]["my"] <= 0 :
                    return False
        return True
                
                    
                
19671