836. Rectangle Overlap

[zeikar]

Problem Link

https://leetcode.com/problems/rectangle-overlap/

Problem Summary

축에 평행한 직사각형 두 개가 주어질 때, 교집합의 넓이가 양수인지 판단하는 문제. 변이나 꼭짓점만 닿는 것은 겹치지 않는 것으로 본다.

Solution

easy지만 생각보다 easy하지 않은 문제.

처음엔 한쪽의 끝점이나 꼭짓점이 상대 직사각형 안에 들어가는지로 판단하려 했다. 그런데 한쪽이 다른 쪽을 품는 경우나 십자 모양으로 겹치는 경우를 놓치고, 경계 처리도 계속 어긋났다.

x축과 y축을 1차원으로 따로 보고, 겹치는 경우 대신 안 겹치는 경우를 생각하면 된다.

선분 [a, b)와 [c, d)가 안 겹치는 경우는 한쪽이 완전히 왼쪽에 있거나 오른쪽에 있는 두 가지뿐이다.

안 겹친다 = b <= c or d <= a

직사각형은 x축이나 y축 중 하나라도 떨어져 있으면 안 겹친다. 두 축의 조건을 or로 묶고 뒤집으면 된다.

Source Code

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        [r1x1, r1y1, r1x2, r1y2] = rec1
        [r2x1, r2y1, r2x2, r2y2] = rec2

        return not ((r1x1 >= r2x2 or r1x2 <= r2x1) or
            (r1y1 >= r2y2 or r1y2 <= r2y1))