X

LEETCODE 1401. Circle and Rectangle Overlapping 解题思路分析

题目大意:

圆和矩形是否有重叠

给你一个以 (radius, x_center, y_center) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2),其中 (x1, y1) 是矩形左下角的坐标,(x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分,请你返回 True ,否则返回 False 。

换句话说,请你检测是否 存在 点 (xi, yi) ,它既在圆上也在矩形上(两者都包括点落在边界上的情况)。

示例 1:

输入:radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出:true
解释:圆和矩形有公共点 (1,0)

示例 2:

输入:radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出:true

示例 3:

输入:radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
输出:true

示例 4:

输入:radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出:false

提示:

  • 1 <= radius <= 2000
  • -10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
  • x1 < x2
  • y1 < y2

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1401

解题思路分析:

这是一道空间几何类型的题目。我们只要将题目的可能性稍加总结,本题也就迎刃而解。

我们定义:

int circleTop=y_center+radius; // 圆形最上端
int circleBottom=y_center-radius; // 圆形最下端
int circleLeft=x_center-radius; // 圆形最左端
int circleRight=x_center+radius; // 圆形最右端
x1 // 矩形最左端
x2 // 矩形最右端
y1 // 矩形最下端
y2 // 矩形最上端
  1. 圆形与矩形完全不相交,该情况下返回false。本情况用代码形容即是:
circleTop<y1||circleBottom>y2||circleLeft>x2||circleRight<x1

2. 圆形在矩形内部,该情况下返回true。本情况用代码形容即是:

circleTop<=y2&&circleBottom>=y1&&circleLeft>=x1&&circleRight<=x2

3. 剩下的情况即是两个图形或在x或者y上有交集,对于这种情况,不论是仅在x上有交集,或者仅在y上有交集,亦或是在x和y上都有交集,我们都无法确定2图形是否相交,比如下图三种情况下两个图形都不相交:

因此,对于剩下的这种情况的判断,我们需要遍历矩形上的每一个点,查看当前点与圆心之间的距离,如果该距离小于等于圆半径,说明他们相交,反之则不相交。

实现代码:

public boolean checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {
    int circleTop=y_center+radius;
    int circleBottom=y_center-radius;
    int circleLeft=x_center-radius;
    int circleRight=x_center+radius;
    if(circleTop<y1||circleBottom>y2||circleLeft>x2||circleRight<x1){
        return false;
    }
    if(circleTop<=y2&&circleBottom>=y1&&circleLeft>=x1&&circleRight<=x2){
        return true;
    }
    for(int i=x1;i<=x2;i++){
        if(getDis(x_center,y_center,i,y1)<=radius) return true;
        if(getDis(x_center,y_center,i,y2)<=radius) return true;
    }
    for(int i=y1;i<=y2;i++){
        if(getDis(x_center,y_center,x1,i)<=radius) return true;
        if(getDis(x_center,y_center,x2,i)<=radius) return true;
    }
    return false;
}
// 计算两点间距离
double getDis(int x1, int y1, int x2, int y2){
   return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Circle and Rectangle Overlapping.

Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Circle and Rectangle Overlapping.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1401-circle-and-rectangle-overlapping-解题思路分析/
Categories: leetcode
kwantong: