圆和矩形是否有重叠
难度:
标签:
题目描述
给你一个以 (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
代码结果
运行时间: 25 ms, 内存: 16.0 MB
/*
* 思路：
* 使用Java Stream实现同样的逻辑：
* 1. 先计算圆心到矩形的最近点。
* 2. 然后计算圆心到这个最近点的距离。
* 3. 最后比较这个距离和圆的半径。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
// 使用stream计算矩形内最靠近圆心的点
int closestX = IntStream.of(x1, x2).boxed().min((a, b) -> Integer.compare(Math.abs(xCenter - a), Math.abs(xCenter - b))).get();
int closestY = IntStream.of(y1, y2).boxed().min((a, b) -> Integer.compare(Math.abs(yCenter - a), Math.abs(yCenter - b))).get();
// 计算圆心到这个点的距离
int distanceX = xCenter - closestX;
int distanceY = yCenter - closestY;
// 使用勾股定理计算距离
int distanceSquared = distanceX * distanceX + distanceY * distanceY;
// 比较距离和半径
return distanceSquared <= radius * radius;
}
}解释
方法:
此题解首先检查圆心是否在矩形外部的某个方向上距离过远，足以使圆完全不与矩形重叠。若圆心在矩形的左侧、右侧、下侧或上侧，且与矩形的距离超过半径，则直接返回False。如果圆心与矩形的某个角的距离在x或y方向超过半径，也会返回False。接着，代码检查圆心是否在矩形的四个角的外侧，如果是，则需要计算圆心到最近角的距离，看其是否小于等于半径的平方，若是，则圆至少与矩形的角接触。如果以上情况都不满足，即圆心在矩形内部或边界上，则返回True，表示圆和矩形重叠。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在判断圆心是否在矩形的四个角之外时，您使用的是平方距离而不是直接计算欧几里得距离？
▷🦆
在执行距离比较时，为什么选择`(x1 - xCenter) > radius`而不是`(x1 - xCenter) >= radius`，即考虑等于半径时的情况？
▷🦆
如果圆心正好在矩形的边上，但没有任何部分进入矩形内部，算法会如何处理这种情况？
▷🦆
算法中有没有考虑圆完全在矩形内部但不接触边界的情况，会返回正确的结果吗？
▷