1401. Circle and Rectangle Overlapping

Problem Overview

A circle and an axis-aligned rectangle overlap when the circle reaches the closest point of the rectangle to its center.

Intuition

A circle and an axis-aligned rectangle overlap when the circle reaches the closest point of the rectangle to its center. Clamp the center into the rectangle bounds to find that point, then compare squared distances so you never need a square root.

Algorithm

1Clamp xCenter into [x1, x2] to get closestX.
2Clamp yCenter into [y1, y2] to get closestY.
3Let dx = xCenter - closestX and dy = yCenter - closestY.
4Return true if dx*dx + dy*dy is at most radius*radius.

Example Walkthrough

Input: radius = 1, center = (0,0), rect = [1,-1,3,1]

1.Closest point on the rectangle is (1,0).
2.Squared distance is 1, equal to radius squared.
3.The shapes touch, which counts as overlap.

Output: true

Common Pitfalls

•Touching the boundary is overlap; use <= not <.
•Work with squared distances to avoid floating point and sqrt.
•If the center lies inside the rectangle, the closest point is the center itself and distance is zero.
•The rectangle is axis-aligned; do not rotate it.

1401.cs

// Approach: Clamp the circle center into the axis-aligned rectangle to get
// the closest point on (or in) the rect. Overlap iff squared distance from
// center to that point is at most radius^2 (avoids sqrt).
// Complexity: O(1) time and O(1) space.
public class Solution
{
    public bool CheckOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2)
    {
        int closestX = Math.Max(x1, Math.Min(x2, xCenter));
        int closestY = Math.Max(y1, Math.Min(y2, yCenter));
        int dx = xCenter - closestX;
        int dy = yCenter - closestY;
        return dx * dx + dy * dy <= radius * radius;
    }
}

Was this solution helpful?