2. Linux.do
  3. Leetcode每日一题 —— 1401. 圆和矩形是否有重叠

Leetcode每日一题 —— 1401. 圆和矩形是否有重叠

SomeBottle 2026-09-19 10:25 1



思路


几何题。首先很明确的是，如果圆中心在矩形内，那么肯定有重叠的部分。


如果圆中心在矩形外，我们应该矩形上离圆最近的一个点。“最近”即要求圆心到矩形上的一个点的连线，使得这个连线最短。

最短距离肯定要找一个垂线，如果圆心在矩形的正左方、正右方、正上方、正下方，显然圆心到边的垂线就是最短的，垂足很容易找到；但如果圆心在斜方向，比如左上方，在边上就找不到垂足了，这种时候角点就是距离圆心最近的矩形点。


代码实现上，就是看 xCenter 和 x1, x2，以及 yCenter 和 y1, y2 的关系。如 xCenter<=x1，那就取 x1，x1<=xCenter<=x2 就取 xCenter，x2<=xCenter 那就取 x2，y 的同理。这样就能找到距离圆心最近的点了。



代码


class Solution {

public:

    bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {

        // 首先先来最简单的检查，如果 xCenter, yCenter 在矩形内，肯定有交叠

        if(x1<=xCenter&&xCenter<=x2&&y1<=yCenter&&yCenter<=y2){

            return true;

        }

        // 其他情况下就是要找到矩形上距离圆最近的点

        double nearestX = max((double)x1, min((double)xCenter, (double)x2));

        double nearestY = max((double)y1, min((double)yCenter, (double)y2));



        double dx = nearestX - xCenter;

        double dy = nearestY - yCenter;

        return dx * dx + dy * dy <= (double)radius * radius;

    }

};
最新回复 (4)
  • Lvvvv 09-19 10:27
    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 = xCenter - closestX;
    
        int dy = yCenter - closestY;
    
        return dx * dx + dy * dy <= radius * radius;
    
    }
    
};
  • CPython 09-19 10:36
    2楼

    刚开始用的两个矩形判断 结果就是有一个样例过不去, 还是看了题解


    class Solution:
    
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
    
        def f(i, j, k):
    
            if i <= k <= j:
    
                return 0
    
            return i - k if k < i else j - k
    
        
    
        x, y = f(x1, x2, xCenter), f(y1, y2, yCenter)
    
        return x * x + y * y <= radius * radius
  • 魔法师 09-20 08:55
    3楼

    我好像想复杂了


    代码


        public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
    
        // 彻底远离的情况
    
        if (x1 > xCenter + radius || y1 > yCenter + radius || x2 < xCenter - radius || y2 < yCenter - radius) {
    
            return false;
    
        }
    
        // 矩形包含圆心的情况
    
        if (x1 < xCenter && y1 < yCenter && x2 > xCenter && y2 > yCenter) {
    
            return true;
    
        }
    
        // 矩形不包含圆心，那矩形的四条线与圆形交点的连线一定包含矩形的部分
    
        int rSquared = radius * radius;
    
        return (checkIntersection(xCenter, yCenter, x1, y1, x2, y2, rSquared) ||
    
                checkIntersection(yCenter, xCenter, y1, x1, y2, x2, rSquared));
    
    }
    

    
    private boolean checkIntersection(int aCenter, int bCenter, int a1, int b1, int a2, int b2, int rSquared) {
    
        // 选择方向上最近的那条边
    
        int recent = Math.abs(a1 - aCenter) > Math.abs(a2 - aCenter) ? a2 : a1;
    
        // 求出两个交点
    
        double offset = Math.sqrt(rSquared - (recent - aCenter) * (recent - aCenter));
    
        double d1 = bCenter - offset;
    
        double d2 = bCenter + offset;
    
        // 判断交点连成的线段是否与矩形的边有重叠部分
    
        return (d1 <= b1 && b1 <= d2) || (d1 <= b2 && b2 <= d2) || (b1 <= d1 && d2 <= b2);
    
    }
  • 编程牛马波比 09-20 09:26
    4楼

    稍微有一点复杂，把圆的位置通过镜像反转的方式放到了方形中心的左下角


    public class Solution {
    
    public bool CheckOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
    
        if(xCenter >= x1 && xCenter <= x2 && yCenter >= y1 && yCenter <= y2) return true;
    

    
        double recxCenter = (double) (x2 + x1)/2;
    
        double recyCenter = (double) (y2 + y1)/2;
    
        
    
        double roundxCenter = recxCenter - Math.Abs(xCenter - recxCenter);
    
        double roundyCenter = recyCenter - Math.Abs(yCenter - recyCenter);
    

    
        if(roundyCenter >= y1 && roundyCenter <= y2) return x1 - roundxCenter <= radius;
    
        if(roundxCenter >= x1 && roundxCenter <= x2) return y1 - roundyCenter <= radius;
    
      
    
        double overlapToRoundCenter = Math.Pow(x1 - roundxCenter, 2) + Math.Pow(y1 - roundyCenter,2);
    
        if (overlapToRoundCenter > Math.Pow(radius, 2)) return false;
    
        
    
        return true;
    
    }
    
}
* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐