[파이썬/python] 백준 - 15973 두 박스

문제

https://www.acmicpc.net/problem/15973

---

문제 설명

1.   2차원 좌표 평면 위에 두 개의 박스 P,Q가 놓여 있다.
2. 각 박스의변은 x 혹은 y축에 평행하다.
3. 두 박스가 서로 교차하는지 여부를 판단하고 싶다.
   1. 내부가 겹쳐있다면 FACE
   2. 선분에서 만난다면 LINE
   3. 한 점에서 만난다면 POINT
   4. 만나지 않는다면 NULL
4. 두 박스의 좌표가 주어질 때 교차 여부를 판단한다. 

 

---

풀이

두 박스의 내부가 겹쳐있는 것을 판단하려면, 임의의 두 좌표가 동일하게 존재해야 한다.

 

하지만 이를 확인하려면 모든 좌표를 검사해야하는데, 문제에서 주어진 좌표의 범위는 $-10^9$에서 $10^9$이기 때문에 모든 범위 내 모든 좌표를 검사하기 어렵다.  

 

따라서 나는 FACE인 조건을 찾기보다는 상대적으로 찾기 쉬운 다른 조건들을 모두 찾은 후 소거법으로 마지막에 FACE를 출력하도록 했다.

1. 만약 첫 번째 정사각형과 두 번째 정사각형의 각 x와 y의 꼭짓점이 모두 동일하다면 POINT를 출력한다.
2. 두 정사각형의 y축 범위와 x축 범위가 겹치지 않았다면 NULL을 출력한다.
3. y축 혹은 x축이 한 줄에서만 겹친다면 LINE을 출력한다.
4. 위 3개의 조건을 만족하지 않는다면 FACE를 출력한다.

---

코드

import sys
input = sys.stdin.readline

px = []
py = []
for i in range(2):
    y1,x1,y2,x2 = map(int,input().split())
    py.append([y2,y1])
    px.append([x2,x1])
py.sort(key = lambda x: (-x[0],-x[1]))
px.sort(key = lambda x: (-x[0],-x[1]))

if py[0][1] == py[1][0] and px[0][1] == px[1][0]:
    print("POINT")
elif not (py[0][1] <= py[1][0] <= py[0][0]) or not (px[0][1] <= px[1][0] <= px[0][0]):
    print("NULL")
elif py[0][1] == py[1][0] or px[0][1] == px[1][0]:
    print("LINE")
else:
    print("FACE")

---

시간복잡도

• 단순 조건분기를 통해 문제를 해결할 수 있다.
• 즉 $O(1)$의 시간복잡도로 문제를 해결할 수 있다.