1401. 圆和矩形是否有重叠

LC每日一题，参考1401. 圆和矩形是否有重叠，难度分1709。

题目

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

如果圆和矩形有重叠的部分，请你返回 true ，否则返回 false 。

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

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形存在公共点 (1,0) 。

输入：radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true

解题思路

• 数学：根据圆与矩形重合的几种可能情况判断。

数学

class Solution {
    public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        //把圆当成矩形看待,判断横向和纵向是否有交叉
        if(xCenter+radius < x1 || xCenter-radius > x2) return false;
        if(yCenter+radius < y1 || yCenter-radius > y2) return false;
        //正方形包裹了圆心
        if(xCenter>=x1 && xCenter<=x2 && yCenter>=y1 && yCenter<=y2) return true;
        boolean ans = false;
        //是否相切
        if(yCenter >= y1 && yCenter <= y2) 
            ans |= dis(xCenter,yCenter,radius,x1,yCenter)
            ||dis(xCenter,yCenter,radius,x2,yCenter);
        if(xCenter >= x1 && xCenter <= x2)
            ans |= dis(xCenter,yCenter,radius,xCenter,y1)
            ||dis(xCenter,yCenter,radius,xCenter,y2);
        //判断圆心距离矩形四个顶点距离是否大于半径
        ans |= dis(xCenter,yCenter,radius,x1,y1)||dis(xCenter,yCenter,radius,x2,y2)
            ||dis(xCenter,yCenter,radius,x1,y2)||dis(xCenter,yCenter,radius,x2,y1); 
        return ans;
    }

    boolean dis(int c1,int c2,int radius,int x,int y) {
        return radius*radius >= (x-c1)*(x-c1) + (y-c2)*(y-c2);
    }
}

复杂度分析

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