~/leetcode$cat1401. Circle and Rectangle Overlapping

The coordinates are integers. I’m wondering if it is enough to check all the integer coordinates of the shape. It should be enough because the most north, west, east and south point of the circle lies on an integer coordinate.

The two cases that I can think of (to simplify this problem) is:

1. The circle is tangent to the rectangle - this is where most north, south, east, west points of the circle connect to the rectangle.
2. The corner of the rectangle touches the edge of the circle - this can be calculated using ((x - xo)^2 + (y - yo)^2) = r^2

So we check 8 things in total: 4 edges of the rectangle and the 4 corners of the rectangle.

The four edges are pretty easy since we just need to check whether circle centre + radius is within the rectangle. For the four corners, we can use the (x^2 + y^2) = r^2 circle formula and see if the distance betweeen the corner and the circle center is less than or equal to r.

Very mathy problem…

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        # circle making
        def distance(x, y):
            return (x - xCenter) ** 2 + (y - yCenter) ** 2

        # check top and bottom edge
        if x1 <= xCenter <= x2 and y1 - radius <= yCenter <= y2 + radius:
            return True

        # check left and right edge
        if x1 - radius <= xCenter <= x2 + radius and y1 <= yCenter <= y2:
            return True

        # check corners
        if distance(x1, y1) <= radius ** 2:
            return True
        if distance(x1, y2) <= radius ** 2:
            return True
        if distance(x2, y1) <= radius ** 2:
            return True
        if distance(x2, y2) <= radius ** 2:
            return True

        return False

Time Complexity: O(1)

Space Complexity: O(1)

Time Taken: 8m 46s

Runtime: 0 ms

Memory: 19.2 MB

Tests Passed: 90/90