【算法积累】圆和矩形是否有重叠

「爱情、让人受尽委屈。」 2022-12-27 02:26 90阅读 0赞

## LeetCode 1401. 圆和矩形是否有重叠 ##

**难度** 中等

给你一个以 (`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

--------------------

**解法** 数学（距离比较）  
题目要求我们判断给定的圆和矩形是否有重叠部分，即是否存在一个点，它既在圆上也在矩形上。我们只需要找到矩形中距离圆心最近的一个点，比较其到圆心的距离与圆的半径的大小关系即可。  
语言：C

bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) { 
        int x, y;
        if (x_center > x2) { 
            x = x2;
        } else if (x_center < x1) { 
            x = x1;
        } else { 
            x = x_center;
        }
        if (y_center > y2) { 
            y = y2;
        } else if (y_center < y1) { 
            y = y1;
        } else { 
            y = y_center;
        }
        int dist_sq = (x - x_center) * (x - x_center) + (y - y_center) * (y - y_center);
        if (dist_sq <= radius * radius) { 
            return true;
        }
        return false;
    }

时间复杂度： O ( 1 ) O(1) O(1)  
空间复杂度： O ( 1 ) O(1) O(1)