问题描述:
- 给定一个圆和一个平行于坐标轴的矩形,判断两者是否重叠。
- 圆的中心为 ( x c , y c ) (xc,yc) (xc,yc),半径为 r r r。
- 矩形左下角点为 ( x 1 , y 1 ) (x1, y1) (x1,y1),右上角点为 ( x 2 , y 2 ) (x2, y2) (x2,y2)。
解题思路:
- 数学题。
- 圆内(包括圆边上)定义了点集:
{ ( x , y ) : ( x − x c ) 2 + ( y − y c ) 2 ≤ r 2 } \{(x,y):(x-xc)^2+(y-yc)^2 \leq r^2\} {(x,y):(x−xc)2+(y−yc)2≤r2} - 矩形内(包括矩形边上)定义了点集:
{ ( x , y ) : x 1 ≤ x ≤ x 2 , y 1 ≤ y ≤ y 2 } \{(x,y):x1\leq x\leq x2,y1\leq y \leq y2\} {(x,y):x1≤x≤x2,y1≤y≤y2} - 解题思路就是求得圆心到矩形的最短距离
d
d
d,判断
d
d
d 与
r
r
r 的关系,可能出现的情况如下:
- 假若 x 1 ≤ x ≤ x 2 x1\leq x\leq x2 x1≤x≤x2 且 y 1 ≤ y ≤ y 2 y1\leq y \leq y2 y1≤y≤y2,则此时圆心在矩形内,即 d = 0 d=0 d=0。
- 假若 x 1 ≤ x c ≤ x 2 x1\leq xc\leq x2 x1≤xc≤x2 或者 y 1 ≤ y c ≤ y 2 y1\leq yc \leq y2 y1≤yc≤y2,则圆心与矩形最近点的连线平行于坐标轴,则此时 d = min ( ∣ x c − x 1 ∣ , ∣ x c − x 2 ∣ ) d = \min(|xc - x1|,|xc-x2|) d=min(∣xc−x1∣,∣xc−x2∣) 或者 d = min ( ∣ y c − y 1 ∣ , ∣ y c − y 2 ∣ ) d = \min(|yc - y1|,|yc-y2|) d=min(∣yc−y1∣,∣yc−y2∣)。
- 其余情况下,其实就是求圆心到矩形四个端点的最近距离,此时:
d = min ( ( x c − x 1 ) 2 , ( x c − x 2 ) 2 ) + min ( ( y c − y 1 ) 2 , ( y c − y 2 ) 2 ) d = \sqrt{\min((xc - x1)^2,(xc-x2)^2)+\min((yc - y1)^2,(yc-y2)^2)} d=min((xc−x1)2,(xc−x2)2)+min((yc−y1)2,(yc−y2)2)
代码实现:
class Solution {
public:
bool checkOverlap(int radius, int xc, int yc, int x1, int y1, int x2, int y2) {
long long dist = xc<x1 or xc>x2 ? min(pow(x1-xc,2),pow(x2-xc,2)):0;
dist += yc<y1 or yc>y2 ? min(pow(y1-yc,2),pow(y2-yc,2)) : 0;
return dist <= radius*radius;
}
};
文章来源地址https://www.toymoban.com/news/detail-501212.html
文章来源:https://www.toymoban.com/news/detail-501212.html
到了这里,关于【leetcode】【2023/6/25】1401. 圆和矩形是否有重叠的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!