Problem

You are given a circle represented as (radius, xCenter, yCenter) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return true if the circle and rectangle are overlapped otherwise returnfalse. In other words, check if there is any point (xi, yi) that belongs to the circle and the rectangle at the same time.

Examples

Example 1

1
2
3

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0).

Example 2

1
2

Input: radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Example 3

1
2

Input: radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Constraints

  • 1 <= radius <= 2000
  • -10^4 <= xCenter, yCenter <= 10^4
  • -10^4 <= x1 < x2 <= 10^4
  • -10^4 <= y1 < y2 <= 10^4

Solution

Method 1 – Geometry (Closest Point)

Intuition

The closest point on the rectangle to the circle’s center determines the minimum distance between the circle and the rectangle. If this distance is less than or equal to the radius, the circle and rectangle overlap.

Approach

  1. For the circle center (xCenter, yCenter), find the closest point (x, y) on the rectangle:
    • Clamp xCenter to the range [x1, x2] to get x.
    • Clamp yCenter to the range [y1, y2] to get y.
  2. Compute the squared distance between (xCenter, yCenter) and (x, y).
  3. If the squared distance is less than or equal to radius^2, return true; otherwise, return false.

Code

1
2
3
4
5
6
7
8
9

class Solution {
public:
    bool checkOverlap(int r, int xc, int yc, int x1, int y1, int x2, int y2) {
        int x = max(x1, min(xc, x2));
        int y = max(y1, min(yc, y2));
        int dx = x - xc, dy = y - yc;
        return dx * dx + dy * dy <= r * r;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func checkOverlap(r, xc, yc, x1, y1, x2, y2 int) bool {
    x := xc
    if x < x1 { x = x1 }
    if x > x2 { x = x2 }
    y := yc
    if y < y1 { y = y1 }
    if y > y2 { y = y2 }
    dx, dy := x-xc, y-yc
    return dx*dx+dy*dy <= r*r
}
1
2
3
4
5
6
7
8

class Solution {
    public boolean checkOverlap(int r, int xc, int yc, int x1, int y1, int x2, int y2) {
        int x = Math.max(x1, Math.min(xc, x2));
        int y = Math.max(y1, Math.min(yc, y2));
        int dx = x - xc, dy = y - yc;
        return dx * dx + dy * dy <= r * r;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun checkOverlap(r: Int, xc: Int, yc: Int, x1: Int, y1: Int, x2: Int, y2: Int): Boolean {
        val x = xc.coerceIn(x1, x2)
        val y = yc.coerceIn(y1, y2)
        val dx = x - xc
        val dy = y - yc
        return dx * dx + dy * dy <= r * r
    }
}
1
2
3
4
5
6

class Solution:
    def checkOverlap(self, r: int, xc: int, yc: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        x = min(max(xc, x1), x2)
        y = min(max(yc, y1), y2)
        dx, dy = x - xc, y - yc
        return dx * dx + dy * dy <= r * r
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn check_overlap(r: i32, xc: i32, yc: i32, x1: i32, y1: i32, x2: i32, y2: i32) -> bool {
        let x = xc.max(x1).min(x2);
        let y = yc.max(y1).min(y2);
        let dx = x - xc;
        let dy = y - yc;
        dx * dx + dy * dy <= r * r
    }
}
1
2
3
4
5
6
7
8

class Solution {
    checkOverlap(r: number, xc: number, yc: number, x1: number, y1: number, x2: number, y2: number): boolean {
        const x = Math.max(x1, Math.min(xc, x2));
        const y = Math.max(y1, Math.min(yc, y2));
        const dx = x - xc, dy = y - yc;
        return dx * dx + dy * dy <= r * r;
    }
}

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(1)