Problem

You are given two positive integers xCorner and yCorner, and a 2D array circles, where circles[i] = [xᵢ, yᵢ, rᵢ] denotes a circle with center at (xᵢ, yᵢ) and radius rᵢ.

There is a rectangle in the coordinate plane with its bottom left corner at the origin and top right corner at the coordinate (xCorner, yCorner). You need to check whether there is a path from the bottom left corner to the top right corner such that the entire path lies inside the rectangle, does not touch or lie inside any circle, and touches the rectangle only at the two corners.

Return true if such a path exists, and false otherwise.

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

Example 1:

Input: xCorner = 3, yCorner = 4, circles = [[2,1,1]]
Output: true
Explanation:

case1

The curve shows a possible path between (0, 0) and (3, 4).

Example 2:

Input: xCorner = 3, yCorner = 3, circles = [[1,1,2]]
Output: false
Explanation:

case2

No path exists from (0, 0) to (3, 3).

Example 3:

Input: xCorner = 3, yCorner = 3, circles = [[2,1,1],[1,2,1]]
Output: false
Explanation:

case3

No path exists from (0, 0) to (3, 3).

Example 4:

Input: xCorner = 4, yCorner = 4, circles = [[5,5,1]]
Output: true
Explanation:

case4

Constraints:

  • 3 <= xCorner, yCorner <= 10⁹
  • 1 <= circles.length <= 1000
  • circles[i].length == 3
  • 1 <= xᵢ, yᵢ, rᵢ <= 10⁹

Test Cases

1
2
class Solution:
    def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import pytest

from solution import Solution


@pytest.mark.parametrize('x, y, circles, expected', [
    (3, 4, [[2, 1, 1]], True),
    (3, 3, [[1, 1, 2]], False),
    (3, 3, [[2, 1, 1], [1, 2, 1]], False),
    (4, 4, [[5, 5, 1]], True),

    (3, 3, [[1,2,1], [1,4,1], [2,5,1], [4,5,1], [5,4,1], [5,2,1], [4,2,1]], True),

    (3, 3, [[2,10,7], [10,2,7]], True),
    (3, 3, [[2,1000,997], [1000,2,997]], True),

    (22742157, 210809967, [[22741186,210810964,200],[22741869,210809432,165],[22742256,210810275,182],[22742089,210809693,129],[22741912,210810128,196],[22741658,210809205,144],[22741648,210809094,118],[22741920,210809808,128]], False),

    (8, 8, [[1,4,1],[3,4,1],[5,4,1],[7,4,1]], False),
])
def test_can_reach_corner(x, y, circles, expected):
    sol = Solution()
    assert sol.canReachCorner(x, y, circles) == expected

Thoughts

直观想法

先看单个圆，看圆和矩形的哪些边相交/相切，如果相交/相切的边的集合如下，则没有通路：

  • 上 & 下
  • 左 & 右
  • 左 & 下
  • 右 & 上

判断圆是否和某个边相交/相切：

圆与线段相交/相切 iff

  • 圆心到任一端点距离 ≤ 半径
  • 或
  • 圆心到线的距离 ≤ 半径 && 两个端点在垂线两边（利用水平垂直特点可以简化计算）

再看多个圆，把相交/相切的圆归为一堆，他们相交/相切的边取并集，最终并集结果如果符合上边四种情况，则没
有通路。

判断两个圆是否相交/相切：

两个圆相交/相切 iff 圆心距离 ≤ 圆心半径和

需要注意，如果一个圆完全在矩形之外，应该直接丢弃。
否则可能会出现一个圆压住上边界，一个圆压住右边界，然后矩形外有一堆圆把前两个圆连接起来。但并不影响通路。
如：3, 3, [[1,2,1], [1,4,1], [2,5,1], [4,5,1], [5,4,1], [5,2,1], [4,2,1]]。

判断圆在矩形外：

圆在矩形外 iff 圆与四边都不相交/相切 && 圆不在矩形内

所有圆/连成一片的圆都判定完，没有出现不通的情况，最后结果就是有通路。

记录已经处理过的圆组成的相连的团簇，对于每个圆，跟所有已有的团簇的圆判定是否相连（注意可能会同时跟多
个团簇相连，导致团簇合并）。

复杂度 O(n²)，n 是 圆的个数。

降低复杂度关键：如何快速计算出所有的团簇，裁剪掉不必要的比较，比如用四叉树。

问题：两个圆心在外边的圆相交，但各自跟上和右边相交，但并不影响通路，如 3, 3, [[2,10,7], [10,2,7]]。

取相交/相切圆的圆心连线中的等比点（该点到两个圆心的距离与两个半径同比），如果该点在矩形外就不连成团簇。

设两个圆分别是 (x1, y1, r1)、(x2, y2, r2)，连线上等比点的位置是 (x, y)，则

x = x1 + (x2 - x1) * r1 / (r1 + r2)，y 类似（要避免浮点运算）。

判定 (x, y) 是否在矩形内。

最难点

取相交/相切圆的圆心连线中的等比点（该点到两个圆心的距离与两个半径同比），如果该点在矩形外就不连成团簇。

这是个平面几何数学知识点。

Code

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
from typing import List

R = 1
L = R << 1
B = L << 1
T = B << 1

TB = T | B
LR = L | R
LB = L | B
RT = R | T


class Cluster:
    def __init__(self, circle: List[int], edges: int):
        self.circles = [circle]
        self.edges = edges # cross edges bit map 0bTBLR

        x, y, r = circle
        self.top = y + r
        self.bottom = y - r
        self.left = x - r
        self.right = x + r

    def merge(self, other: 'Cluster'):
        self.circles.extend(other.circles)
        self.edges |= other.edges

        self.top = max(self.top, other.top)
        self.bottom = min(self.bottom, other.bottom)
        self.left = min(self.left, other.left)
        self.right = max(self.right, other.right)

    def is_out_of_bound(self, circle: List[int]):
        x, y, r = circle
        return x + r < self.left or x - r > self.right or y + r < self.bottom or y - r > self.top


class Solution:
    def canReachCorner(self, xCorner: int, yCorner: int, circles: List[List[int]]) -> bool:
        clusters = []
        for circle in circles:
            edges, out_of_rect = self._calc_crossed_edges(xCorner, yCorner, circle)
            if self._is_unreachable(edges):
                return False

            if out_of_rect:
                continue

            new_clusters = []
            this_cluster = Cluster(circle, edges)
            for cluster in clusters:
                # A quick prune.
                if cluster.is_out_of_bound(circle):
                    new_clusters.append(cluster)
                    continue

                for circle2 in cluster.circles:
                    if self._are_circles_connected_inside_rect(circle, circle2, xCorner, yCorner):
                        this_cluster.merge(cluster)
                        if self._is_unreachable(this_cluster.edges):
                            return False
                        break
                else:
                    new_clusters.append(cluster)

            new_clusters.append(this_cluster)
            clusters = new_clusters

        return True

    def _are_circles_connected(self, circle1: List[int], circle2: List[int]) -> bool:
        x1, y1, r1 = circle1
        x2, y2, r2 = circle2

        # Prune by bound box.
        if x2 + r2 < x1 - r1 or x2 - r2 > x1 + r1 or y2 + r2 < y1 - r1 or y2 - r2 > y1 + r1:
            return False

        distance_square = (x1 - x2) ** 2 + (y1 - y2) ** 2
        radius_sum_square = (r1 + r2) ** 2
        return distance_square <= radius_sum_square

    def _are_circles_connected_inside_rect(self, circle1, circle2, xCorner, yCorner) -> bool:
        if not self._are_circles_connected(circle1, circle2):
            return False

        x1, y1, r1 = circle1
        x2, y2, r2 = circle2

        # (x1, y1)--(x, y) : (x, y)--(x2, y2) = r1 : r2
        # Check if (x, y) inside rect.
        if (-x1 * (r1 + r2) <= (x2 - x1) * r1 <= (xCorner - x1) * (r1 + r2) and
            -y1 * (r1 + r2) <= (y2 - y1) * r1 <= (yCorner - y1) * (r1 + r2)):
            return True

        return False

    def _is_h_line_cross_circle(self, left: int, right: int, y: int, circle: List[int]) -> bool:
        cx, cy, r = circle

        # Check if line is far away from circle.
        if abs(y - cy) > r:
            return False

        # Check if left endpoint inside circle.
        r_square = r ** 2
        if (left - cx) ** 2 + (y - cy) ** 2 <= r_square:
            return True

        # Check if right endpoint inside circle.
        if (right - cx) ** 2 + (y - cy) ** 2 <= r_square:
            return True

        # Check if the two endpoints apart from the perpendicular line.
        if left < cx < right:
            return True

        return False

    def _is_v_line_cross_circle(self, bottom: int, top: int, x: int, circle: List[int]) -> bool:
        cx, cy, r = circle

        # Check if line is far away from circle.
        r_square = r ** 2
        if abs(x - cx) > r:
            return False

        # Check if bottom endpoint inside circle.
        if (x - cx) ** 2 + (bottom - cy) ** 2 <= r_square:
            return True

        # Check if top endpoint inside circle.
        if (x - cx) ** 2 + (top - cy) ** 2 <= r_square:
            return True

        # Check if the two endpoints apart from the perpendicular line.
        if bottom < cy < top:
            return True

        return False

    def _calc_crossed_edges(self, xCorner, yCorner, circle) -> tuple[int, bool]:
        edges = 0

        if self._is_h_line_cross_circle(0, xCorner, yCorner, circle):
            edges |= T

        if self._is_h_line_cross_circle(0, xCorner, 0, circle):
            edges |= B

        if self._is_v_line_cross_circle(0, yCorner, xCorner, circle):
            edges |= R

        if self._is_v_line_cross_circle(0, yCorner, 0, circle):
            edges |= L

        cx, cy, _ = circle
        out_of_rect = edges == 0 and not (0 < cx < xCorner and 0 < cy < yCorner)

        return edges, out_of_rect

    def _is_unreachable(self, edges: int) -> bool:
        return edges & TB == TB or edges & LR == LR or edges & LB == LB or edges & RT == RT

Test cases for solution inner methods:

solution_inner_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import pytest

from solution import Solution


@pytest.mark.parametrize('circle1, circle2, expected', [
    ([2, 1, 1], [1, 2, 1], True),
    ([2, 1, 1], [4, 2, 1], False),
])
def test_circles_connected(circle1, circle2, expected):
    sol = Solution()
    assert sol._are_circles_connected(circle1, circle2) == expected


@pytest.mark.parametrize('circle1, circle2, x, y, expected', [
    ([2, 1, 1], [1, 2, 1], 3, 3, True),
    ([2, 1, 1], [1, 2, 1], 2, 2, True),
    ([2, 1, 1], [1, 2, 1], 1, 1, False),
    ([2, 1, 1], [4, 2, 1], 3, 3, False),
    ([2,1000,997], [1000,2,997], 3, 3, False),
    ([22741912, 210810128, 196], [22741920, 210809808,128], 22742157, 210809967, True),
])
def test_circles_connected_inside_rect(circle1, circle2, x, y, expected):
    sol = Solution()
    assert sol._are_circles_connected_inside_rect(circle1, circle2, x, y) == expected


@pytest.mark.parametrize('left, right, y, circle, expected', [
    [0, 3, 0, [2,1,1], True],
    [0, 3, 4, [2,1,1], False],

    [0, 3, 0, [1,1,2], True],
    [0, 3, 3, [1,1,2], True],

    [0, 3, 3, [2,1,1], False],
    [0, 3, 0, [2,1,1], True],
    [0, 3, 3, [1,2,1], True],
    [0, 3, 0, [1,2,1], False],
])
def test_h_line_cross_circle(left, right, y, circle, expected):
    sol = Solution()
    assert sol._is_h_line_cross_circle(left, right, y, circle) == expected


@pytest.mark.parametrize('bottom, top, x, circle, expected', [
    [0, 4, 0, [2,1,1], False],
    [0, 4, 4, [2,1,1], False],

    [0, 3, 0, [1,1,2], True],
    [0, 3, 3, [1,1,2], True],

    [0, 3, 3, [2,1,1], True],
    [0, 3, 0, [2,1,1], False],
    [0, 3, 3, [1,2,1], False],
    [0, 3, 0, [1,2,1], True],
])
def test_v_line_cross_circle(bottom, top, x, circle, expected):
    sol = Solution()
    assert sol._is_v_line_cross_circle(bottom, top, x, circle) == expected


@pytest.mark.parametrize('x, y, circle, expected', [
    [3, 4, [2, 1, 1], (0b0101, False)],
    (3, 3, [1, 1, 2], (0b1111, False)),
    (3, 3, [2, 1, 1], (0b0101, False)),
    (3, 3, [1, 2, 1], (0b1010, False)),
    (4, 4, [5, 5, 1], (0b0000, True)),
    (10, 10, [5, 5, 1], (0b0000, False)),
])
def test_calc_crossed_edges(x, y, circle, expected):
    sol = Solution()
    assert sol._calc_crossed_edges(x, y, circle) == expected
hard difficult
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~