一、题目描述
给你两个正整数 xCorner 和 yCorner 和一个二维整数数组 circles ,其中 circles[i] = [xi, yi, ri] 表示一个圆心在 (xi, yi) 半径为 ri 的圆。
坐标平面内有一个左下角在原点,右上角在 (xCorner, yCorner) 的矩形。你需要判断是否存在一条从左下角到右上角的路径满足:路径 完全 在矩形内部,不会 触碰或者经过 任何 圆的内部和边界,同时 只 在起点和终点接触到矩形。
如果存在这样的路径,请你返回 true ,否则返回 false 。
示例 1:
输入:X = 3, Y = 4, circles = [[2,1,1]]
输出:true
解释:
黑色曲线表示一条从 (0, 0) 到 (3, 4) 的路径。
示例 2:
输入:X = 3, Y = 3, circles = [[1,1,2]]
输出:false
解释:
不存在从 (0, 0) 到 (3, 3) 的路径。
示例 3:
输入:X = 3, Y = 3, circles = [[2,1,1],[1,2,1]]
输出:false
解释:
不存在从 (0, 0) 到 (3, 3) 的路径。
示例 4:
输入:X = 4, Y = 4, circles = [[5,5,1]]
输出:true
解释:
提示:
3 <= xCorner, yCorner <= 109
1 <= circles.length <= 1000
circles[i].length == 3
1 <= xi, yi, ri <= 109
二、解题思路
可以将矩形的四条边以及所有的圆视为图中的点,若圆与圆相交或者圆与矩形边相交或包含,那么就在其对应的点连上一条边。在完成建图后,若矩形的上边和下边,左边和右边,上边和右边,左边和下边这四组点中有任意一组处于同一个连通块中,那么就说明出现了阻隔线,不存在可达的路径,否则必然存在可达的路径。关于连通块的处理可以使用并查集,那么接下来的问题就变成了判断圆与矩形边相交或包含,以及圆与圆相交。
对于圆与圆相交时比较简单的,只需判断两圆的圆心距离是否小于等于两圆的半径之和就行了。
对于圆和矩形边的判断则相对复杂一点,可以分成两种情况:
1、若矩形边的某个端点出现在圆的内部,那么圆必然包含矩形边或者与矩形边相交。判断点是否出现在圆内部只需要判断点到圆心的距离是否小于等于圆的半径就行了。
2、若矩形边的两个端点都在圆的外部,那么就需要从圆心向矩形边所在的直线做一条垂线,这条垂线的长度必须要小于等于半径的长度,同时矩形边的两个端点必须位于这条垂线的两侧。由于题目中矩形的边都是水平或者竖直的,因此矩形边的两个端点必然在某个维度上是一样的,这个维度的值与圆心在这个维度值之差就是垂线的长度,而另一个维度的值只需分别处于圆心另一个维度值的两侧就行了。
参考:https://zhuanlan.zhihu.com/p/720471180
三、代码
class Solution(object):def canReachCorner(self, xCorner, yCorner, circles):""":type xCorner: int:type yCorner: int:type circles: List[List[int]]:rtype: bool"""def find(fa, x):if fa[x] != x:fa[x] = find(fa, fa[x])return fa[x]def union(fa, x, y):fa_x = find(fa, x)fa_y = find(fa, y)if fa_x != fa_y:fa[fa_x] = fa_ydef dis(p1, p2):return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2def in_circle(circle, p):return dis((circle[0], circle[1]), p) <= circle[2] ** 2def rec_cross(circle, p1, p2):in1 = in_circle(circle, p1)in2 = in_circle(circle, p2)if in1 or in2:return Trueif p1[0] == p2[0]:same = 0else:same = 1other = 1 - sameif p1[same] < circle[same] - circle[2] or p1[same] > circle[same] + circle[2]:return Falseif max(p1[other], p2[other]) < circle[other] or min(p1[other], p2[other]) > circle[other]:return Falsereturn Truedef circle_cross(circle1, circle2):return dis((circle1[0], circle1[1]), (circle2[0], circle2[1])) <= (circle1[2] + circle2[2]) ** 2def cross_in_rec(circle1, circle2, xCorner, yCorner):if circle1[0] * circle2[2] + circle2[0] * circle1[2] >= xCorner * (circle1[2] + circle2[2]):return Falseif circle1[1] * circle2[2] + circle2[1] * circle1[2] >= yCorner * (circle1[2] + circle2[2]):return Falsereturn Truen = len(circles)fa = [index for index in range(n + 4)]rec_points = [(0, 0), (0, yCorner), (xCorner, yCorner), (xCorner, 0)]for i in range(n):for p in range(4):if rec_cross(circles[i], rec_points[p], rec_points[(p + 1) % 4]):union(fa, i, n + p)for j in range(i + 1, n):if circle_cross(circles[i], circles[j]) and cross_in_rec(circles[i], circles[j], xCorner, yCorner):union(fa, i, j)if find(fa, n) == find(fa, n + 2):return Falseif find(fa, n + 1) == find(fa, n + 3):return Falseif find(fa, n) == find(fa, n + 3):return Falseif find(fa, n + 1) == find(fa, n + 2):return Falsereturn True