백준 15973 - 두 박스

문제설명

제한사항 및 입출력

이 문제는 서브태스크가 있는 문제이다. 하지만 신경쓰지 말고 한 번에 100점을 받아보자!

풀이

좌표평면 위의 두 직사각형이 어떤 위상으로 교차하는지를 판별하는 문제이다.

별 생각없이 문제를 봤을 땐 전체 좌표평면을 0으로 초기화한 후 직사각형의 범위를 1로 칠하면서 2의 개수(겹쳐진 면적)를 확인하려고 했는데 좌표의 범위가 무려 -1e9 ~ 1e9이다! 절대로 이 방법으로는 풀 수 없다는 것을 직감한 후 다시 생각해보았다.

 

결국 직접 비교하는 구현은 엄청 넓은 사각형이 주어지게 된다면 필연적으로 시간초과가 난다. 주어지는 두 좌표(왼쪽 하단 꼭짓점, 오른쪽 상단 꼭짓점)만 가지고 한 번에 비교할 수 있는 방법이 있을까 고민했다.

x축에서 겹치는 구간 범위와 y축에서 겹치는 구간 범위를 0과 비교한다면 답이 나온다!

 

NULL(겹치지 않음): x축에서 겹치는 구간 범위 < 0 OR y축에서 겹치는 구간 범위 < 0

POINT(한 점만 겹침): x축에서 겹치는 구간 범위 == 0 AND y축에서 겹치는 구간 범위 == 0

LINE(선이 겹침): x축에서 겹치는 구간 범위 == 0 OR y축에서 겹치는 구간 범위 == 0

FACE(부분이 겹침): 그 외의 경우

-> 이 방법은 모든 선분이 x축, y축과 평행한 직사각형이기 때문에 성립한다.

내 코드

x1, y1, x2, y2 = mis()
x3, y3, x4, y4 = mis()

dx = min(x2, x4) - max(x1, x3)
dy = min(y2, y4) - max(y1, y3)

if dx < 0 or dy < 0:
    print("NULL")
elif dx == 0 and dy == 0:
    print("POINT")
elif dx == 0 or dy == 0:
    print("LINE")
else:
    print("FACE")

고찰

문제를 풀고 난 후 만약 도형이 직사각형이 아닌 다른 도형이었다면 어땠을지 생각해보았다. 임의의 네 점을 잇는 두 사각형의 교차판정을 하는 문제라면? (사다리꼴, 평행사변형 등)