1401. 圆和矩形是否有重叠
题目描述
给你一个以 (radius, xCenter, yCenter)
表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2)
,其中 (x1, y1)
是矩形左下角的坐标,而 (x2, y2)
是右上角的坐标。
如果圆和矩形有重叠的部分,请你返回 true
,否则返回 false
。
换句话说,请你检测是否 存在 点 (xi, yi)
,它既在圆上也在矩形上(两者都包括点落在边界上的情况)。
示例 1 :
输入:radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1 输出:true 解释:圆和矩形存在公共点 (1,0) 。
示例 2 :
输入:radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1 输出:false
示例 3 :
输入:radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1 输出:true
提示:
1 <= radius <= 2000
-104 <= xCenter, yCenter <= 104
-104 <= x1 < x2 <= 104
-104 <= y1 < y2 <= 104
解法
方法一:数学
对于一个点 \((x, y)\),它到圆心 \((xCenter, yCenter)\) 的最短距离为 \(\sqrt{(x - xCenter)^2 + (y - yCenter)^2}\),如果这个距离小于等于半径 \(radius\),那么这个点就在圆内(包括边界)。
而对于矩形内(包括边界)的点,它们的横坐标 \(x\) 满足 \(x_1 \leq x \leq x_2\),纵坐标 \(y\) 满足 \(y_1 \leq y \leq y_2\)。要判断圆和矩形是否有重叠的部分,相当于在矩形内找到一个点 \((x, y)\),使得 \(a = |x - xCenter|\) 和 \(b = |y - yCenter|\) 都取到最小值,此时若 \(a^2 + b^2 \leq radius^2\),则说明圆和矩形有重叠的部分。
因此,问题转化为求 \(x \in [x_1, x_2]\) 时 \(a = |x - xCenter|\) 的最小值,以及 \(y \in [y_1, y_2]\) 时 \(b = |y - yCenter|\) 的最小值。
对于 \(x \in [x_1, x_2]\):
- 如果 \(x_1 \leq xCenter \leq x_2\),那么 \(|x - xCenter|\) 的最小值为 \(0\);
- 如果 \(xCenter \lt x_1\),那么 \(|x - xCenter|\) 的最小值为 \(x_1 - xCenter\);
- 如果 \(xCenter \gt x_2\),那么 \(|x - xCenter|\) 的最小值为 \(xCenter - x_2\)。
同理,我们可以求出 \(y \in [y_1, y_2]\) 时 \(|y - yCenter|\) 的最小值。以上我们可以统一用函数 \(f(i, j, k)\) 来处理。
即 \(a = f(x_1, x_2, xCenter)\), \(b = f(y_1, y_2, yCenter)\),如果 \(a^2 + b^2 \leq radius^2\),则说明圆和矩形有重叠的部分。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|