1401.圆和矩形是否有重叠：找最近点（三种可能）

【LetMeFly】1401.圆和矩形是否有重叠：找最近点（三种可能）

力扣题目链接：https://leetcode.cn/problems/circle-and-rectangle-overlapping/

给你一个以 (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$方向上距离圆心最近的最近点。

x方向上，圆心在$xCenter$，矩形在$x$方向上的范围（投影）是线段$[x1, x2]$，所以离圆心最近的点$x$坐标有三种可能：

1. 线段在圆心右边（$x1 > xCenter$），最近点是$x1$；
2. 线段在圆心左边（$x2 < xCenter$），最近点是$x2$；
3. 线段覆盖圆心（$x1 \le xCenter \le x2$），最近点是$xCenter$。

y方向上同理。

知道了矩形距离圆心的最近坐标$(x, y)$后，我们只需要判断这个点是否在圆内，即该点到圆心的距离的平方$(x - xCenter)^2 + (y - yCenter)^2$是否$\leq$圆半径的平方$radius^2$即可。

时空复杂度

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

归纳

这三种情况也可以通过一个最大值和最小值的判断得到：

• $x = \max(x1, \min(xCenter, x2))$
• $y = \max(y1, \min(yCenter, y2))$

AC代码

C++

/*
 * @LastEditTime: 2026-09-19 08:27:16
 */
class Solution {
private:
    inline int getClosest(int center, int x1, int x2) {
        if (x1 > center) {
            return x1;
        } else if (x2 < center) {
            return x2;
        } else {
            return center;
        }
    }
public:
    bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int x = getClosest(xCenter, x1, x2);
        int y = getClosest(yCenter, y1, y2);
        return (x - xCenter) * (x - xCenter) + (y - yCenter) * (y - yCenter) <= radius * radius;
    }
};

Python

'''
LastEditTime: 2026-09-19 08:43:25
'''
class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        x = max(x1, min(xCenter, x2))
        y = max(y1, min(yCenter, y2))
        return (x - xCenter) ** 2 + (y - yCenter) ** 2 <= radius ** 2

Java

/*
 * @LastEditTime: 2026-09-19 08:39:53
 */
class Solution {
    private int getClosest(int c, int a, int b) {
        if (a > c) {
            return a;
        } else if (b < c) {
            return b;
        } else {
            return c;
        }
    }

    private int p(int a) {
        return a * a;
    }

    public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int x = getClosest(xCenter, x1, x2);
        int y = getClosest(yCenter, y1, y2);
        return p(x - xCenter) + p(y - yCenter) <= p(radius);
    }
}

Go

/*
 * @LastEditTime: 2026-09-19 08:38:52
 */
package main

func getClosest(center, x1, x2 int) int {
    if x1 > center {
        return x1
    } else if x2 < center {
        return x2
    } else {
        return center
    }
}

func getPow(x int) int {
    return x * x
}

func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
    x := getClosest(xCenter, x1, x2)
    y := getClosest(yCenter, y1, y2)
    return getPow(x - xCenter) + getPow(y - yCenter) <= getPow(radius)
}

Rust

/*
 * @LastEditTime: 2026-09-19 08:46:21
 */
impl Solution {
    fn get_closest(c: i32, a: i32, b: i32) -> i32 {
        if a > c {
            a
        } else if b < c {
            b
        } else {
            c
        }
    }

    fn p(a: i32) -> i32 {
        a * a
    }

    pub fn check_overlap(radius: i32, x_center: i32, y_center: i32, x1: i32, y1: i32, x2: i32, y2: i32) -> bool {
        let x = Self::get_closest(x_center, x1, x2);
        let y = Self::get_closest(y_center, y1, y2);
        Self::p(x - x_center) + Self::p(y - y_center) <= Self::p(radius)
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源