Skip to content

Latest commit

 

History

History

1401.Circle and Rectangle Overlapping

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
images
images
 
 
README.md
README.md
 
 
README_EN.md
README_EN.md
 
 
Solution.cpp
Solution.cpp
 
 
Solution.go
Solution.go
 
 
Solution.java
Solution.java
 
 
Solution.py
Solution.py
 
 

README.md

1401. 圆和矩形是否有重叠

English Version

题目描述

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

解法

方法一：数学

计算矩形离圆最近的点和圆心的距离是否小于等于半径即可。

Python3

class Solution:
    def checkOverlap(
        self,
        radius: int,
        xCenter: int,
        yCenter: int,
        x1: int,
        y1: int,
        x2: int,
        y2: int,
    ) -> bool:
        dx = dy = 0
        if x1 > xCenter:
            dx = xCenter - x1
        elif x2 < xCenter:
            dx = xCenter - x2
        if y1 > yCenter:
            dy = yCenter - y1
        elif y2 < yCenter:
            dy = yCenter - y2
        return dx * dx + dy * dy <= radius * radius

Java

class Solution {
    public boolean checkOverlap(
        int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int dx = x1 > xCenter ? x1 - xCenter : (x2 < xCenter ? xCenter - x2 : 0);
        int dy = y1 > yCenter ? y1 - yCenter : (y2 < yCenter ? yCenter - y2 : 0);
        return dx * dx + dy * dy <= radius * radius;
    }
}

C++

class Solution {
public:
    bool checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int dx = x1 > xCenter ? x1 - xCenter : (x2 < xCenter ? xCenter - x2 : 0);
        int dy = y1 > yCenter ? y1 - yCenter : (y2 < yCenter ? yCenter - y2 : 0);
        return dx * dx + dy * dy <= radius * radius;
    }
};

Go

func checkOverlap(radius int, xCenter int, yCenter int, x1 int, y1 int, x2 int, y2 int) bool {
	dx, dy := 0, 0
	if x1 > xCenter {
		dx = x1 - xCenter
	} else if x2 < xCenter {
		dx = x2 - xCenter
	}
	if y1 > yCenter {
		dy = y1 - yCenter
	} else if y2 < yCenter {
		dy = y2 - yCenter
	}
	return dx*dx+dy*dy <= radius*radius
}

...