원과 축에 나란한 직사각형이 겹치는지 판정하는 문제.

Solution

일단 좌표 범위가 작아서 테두리의 정수 점을 전부 돌려봤다. 입력이 전부 정수라 가장 가까운 점도 정수라서 이걸로도 통과는 된다.

근데 그럴 필요가 없다. 원 중심에서 가장 가까운 직사각형 위의 점 하나만 보면 되고, 그 점은 좌표를 구간에 자른 (min(max(x1, xCenter), x2), min(max(y1, yCenter), y2))다. 거기까지의 거리가 반지름 이하면 겹친다.

왜 저 점이냐면, 직사각형이 두 구간의 곱이라 x 조건과 y 조건이 독립이고 거리 제곱도 (x - cx)^2 + (y - cy)^2로 항이 나뉜다. 그러면 각 항을 따로 최소로 만들어주면 된다. 직사각형 안의 아무 점이나 잡아서 x를 cx 쪽으로 벽까지 밀고 y도 같은 식으로 밀면 항상 저 점에 도착하고, 미는 동안 거리가 줄기만 하니까 저게 최소다.

처음엔 직사각형 중심에서 원 중심으로 선을 그어 만나는 점인 줄 알았는데 아니었다... 공식에 직사각형 중심은 아예 안 들어간다. 긴 벽 앞에 서면 제일 가까운 점이 벽 한가운데가 아니라 내 바로 앞인 것과 같다.

시간복잡도는 O(1). 836이랑 같은 아이디어다. 1차원씩 따로 생각하기.

Source Code

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        x = min(max(x1, xCenter), x2)
        y = min(max(y1, yCenter), y2)

        return (x - xCenter)**2 + (y - yCenter)**2 <= radius**2

1401. Circle and Rectangle Overlapping

Problem Link

Problem Summary

Solution

Source Code