Medium

题目描述

给你一个以 (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
  • -10^4 <= xCenter, yCenter <= 10^4
  • -10^4 <= x1 < x2 <= 10^4
  • -10^4 <= y1 < y2 <= 10^4

解题思路

这道题考查的是几何计算中圆和矩形的相交判断。关键思路是找到矩形上距离圆心最近的点，然后判断这个点到圆心的距离是否小于等于半径。

主要思路：

  1. 找到最近点：对于圆心 (xCenter, yCenter)，我们需要找到矩形上距离它最近的点 (closestX, closestY)

    • 如果圆心的 x 坐标在矩形的 x 范围内，则 closestX = xCenter，否则取边界值
    • 如果圆心的 y 坐标在矩形的 y 范围内，则 closestY = yCenter，否则取边界值

  2. 计算距离：计算最近点到圆心的距离平方，避免开方运算提高效率

  3. 判断重叠：如果距离平方小于等于半径的平方，则说明有重叠

具体实现：

  • closestX = max(x1, min(xCenter, x2))：将圆心 x 坐标限制在 [x1, x2] 范围内
  • closestY = max(y1, min(yCenter, y2))：将圆心 y 坐标限制在 [y1, y2] 范围内
  • 比较 (closestX - xCenter)² + (closestY - yCenter)² ≤ radius²

这种方法时间复杂度为 O(1)，空间复杂度也为 O(1)，是最优解法。

代码实现

class Solution {
public:
    bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        // 找到矩形上距离圆心最近的点
        int closestX = max(x1, min(xCenter, x2));
        int closestY = max(y1, min(yCenter, y2));
        
        // 计算最近点到圆心的距离平方
        int dx = closestX - xCenter;
        int dy = closestY - yCenter;
        int distanceSquared = dx * dx + dy * dy;
        
        // 判断是否小于等于半径平方
        return distanceSquared <= radius * radius;
    }
};

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        # 找到矩形上距离圆心最近的点
        closestX = max(x1, min(xCenter, x2))
        closestY = max(y1, min(yCenter, y2))
        
        # 计算最近点到圆心的距离平方
        dx = closestX - xCenter
        dy = closestY - yCenter
        distanceSquared = dx * dx + dy * dy
        
        # 判断是否小于等于半径平方
        return distanceSquared <= radius * radius

public class Solution {
    public bool CheckOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        // 找到矩形上距离圆心最近的点
        int closestX = Math.Max(x1, Math.Min(xCenter, x2));
        int closestY = Math.Max(y1, Math.Min(yCenter, y2));
        
        // 计算最近点到圆心的距离平方
        int dx = closestX - xCenter;
        int dy = closestY - yCenter;
        int distanceSquared = dx * dx + dy * dy;
        
        // 判断是否小于等于半径平方
        return distanceSquared <= radius * radius;
    }
}

var checkOverlap = function(radius, xCenter, yCenter, x1, y1, x2, y2) {
    // 找到矩形上距离圆心最近的点
    const closestX = Math.max(x1, Math.min(xCenter, x2));
    const closestY = Math.max(y1, Math.min(yCenter, y2));
    
    // 计算最近点到圆心的距离平方
    const dx = closestX - xCenter;
    const dy = closestY - yCenter;
    const distanceSquared = dx * dx + dy * dy;
    
    // 判断是否小于等于半径平方
    return distanceSquared <= radius * radius;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(1) - 只需要进行常数次数的数学运算
空间复杂度O(1) - 只使用了常数个额外变量