LC 3235. 判断矩形的两个角落是否可达

https://leetcode.cn/problems/check-if-the-rectangle-corner-is-reachable/description/

这题看了题解大致知道是什么意思了：整个过程分为两步：

  1. 先对圆检查对矩形的左上半部分和右下半部分进行覆盖检查。
  2. 然后检查每个圆之间的连接情况
  3. 如果最后发现上半部分和下半部分之间出现连接的话，那么认为是没有办法穿越过来的。
class Solution:
    def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) -> bool:
        n = len(circles)
        uf = [-1] * (n + 2)

        def find(x):
            while uf[x] != -1:
                x = uf[x]
            res = x
            while uf[x] != -1:
                r = uf[x]
                uf[x] = res
                x = r
            return res

        def merge(a, b):
            a, b = find(a), find(b)
            if a != b:
                uf[a] = b

        for i in range(n):
            ox, oy, r = circles[i]
            if ox - r <= 0 or oy + r >= Y:
                merge(i, n)
            if ox + r >= X or oy - r <= 0:
                merge(i, n + 1)

            for j in range(i):
                x2, y2, r2 = circles[j]
                if (ox - x2) ** 2 + (oy - y2) ** 2 <= (r + r2) ** 2:
                    merge(i, j)

            if find(n) == find(n + 1):
                return False
        return True