題目出處
1401. Circle and Rectangle Overlapping
難度
medium
題目分類
Math, Geometry
2026-09-20 一刷
個人範例程式碼 - 一刷 (2026/09/20)
class Solution:
def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
# 確認在何處 x 最近，先確認是否 circle 在右側 (比 x2 更大)，再確認是否在左側 (比 x1 更小)
# 如果都不是 x1, x2，那圓原本來就在矩形 x1 ~ x2 範圍裡面
closest_x = max(x1, min(xCenter, x2))
closest_y = max(y1, min(yCenter, y2))
dx = xCenter - closest_x
dy = yCenter - closest_y
return dx*dx + dy*dy <= radius*radius # 直線距離在半徑範圍內
算法說明
數學題目，核心概念是透過計算矩形離圓心最近的 x, y 位置，計算此距離是否有比半徑短。
- 找到離圓心最近的 x, y
以 x 來說，有三種可能
- 左側：xCenter <= x1
- 中間：x1 <= xCenter <= x2
- 右側：x2 <= xCenter
可以整理為 max(x1, min(x2, xCenter))
min(x2, xCenter)：判斷 x2 (矩形右側) -> 可以決定圓是否在矩形右方
max(x1, min(x2, xCenter))：判斷 x1 (矩形左側) -> 可以決定圓是否在矩形左方
如果答案不是 x1, x2，表示圓心已經在 x1~x2 範圍內 (還需要判斷上下是否也在內)
- 再判斷是否在半徑範圍內
用 dx, dy 算出最短距離是否小於半徑，表示就在圓內 （或等於的情況，表示有交點）
Time Complexity
O(1)
Space Complexity
O(1)