백준 문제풀이 : (15973) 두 박스 - c/c++

문제 주소 : https://www.acmicpc.net/problem/15973

15973번: 두 박스

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	512 MB	SILVER 1	수학 / 기하학 / 많은 조건 분기

 

 

문제

---

 

풀이

---

 

코딩 알고리즘이 필요하다기보다는 수학적 아이디어가 필요한 문제였습니다. 하지만 그렇다고 복잡한 공식이 필요하진 않았고, 박스 Q가 P의 근처에서 움직일 수 있는 경로를 따져보며 정리해보니 생각보다 쉽게 풀렸습니다. 

(좌표 입력은 P>Q 순서로 받음)

 

우선 두 박스의 각 좌표는 아래의 변수로 정의합니다.

 

박스 P의 좌측 하단 좌표 : (x, y)

박스 P의 우측 상단 좌표 : (x', y')

 

박스 P의 좌측 하단 좌표 : (a, b)

박스 P의 우측 상단 좌표 : (a', b')

 

문제에서는 P와 Q 두 박스가 어떤 관계에 있는지를 출력하라고 요구합니다. 위 문제에도 적혀있지만, 아래에 다시 가볍게 정리해보면 다음과 같습니다.

 

POINT : P와 Q의 꼭짓점이 맞붙어있는 상태

LINE : P와 Q의 면이 맞붙어있는 상태

FACE : P와 Q가 중첩되어있는 상태

NULL : P와 Q가 떨어져있는 상태

 

우선, 두 박스가 맞붙어있는 상태인 LINE과 POINT를 중심으로 Q가 움직일 수 있는 경로를 그려봅니다. 아래 그림의 갈색 선과 같습니다. 

 

두 박스 간의 관계를 위 그림에 맞춰 다음과 같이 재정의 할 수 있습니다.

 

POINT : Q의 두 꼭짓점이, 갈색 선과 P의 꼭짓점에 각각 닿아있다.

LINE : Q의 두 면이, 갈색 선과 P의 면에 각각 닿아있다.

FACE : Q는 갈색 선 안쪽에 위치해있다. (갈색 선의 면과는 접점이 없다.)

NULL : Q의 어느 한 면이 무조건 갈색 선 바깥에 위치해있다. (P와 접점이 없다.)

 

위 상태를 코드로 구현하기 위해, 갈색 선의 네 모서리에 대한 정보도 그림에 표시해줍니다.

 

 

 

그럼 이제 문제를 풀 수 있는 모든 준비가 끝났습니다. 코드 내에서는 if 문을 활용하여, POINT > LINE > FACE > NULL 순으로 걸러줄 것입니다.

 

POINT는 가장 걸러내기 쉽습니다. Q의 네 모서리가 각각 호응되는 갈색 상자의 네 모서리와 맞붙어있는지를 검사하면 간단히 도출할 수 있습니다.

 

LINE의 경우는, Q가 P의 면에 딱 붙어서 한 바퀴를 회전한다고 했을 때, 우측 위 모서리인 (A', B')의 경로를 체크해주면 됩니다. LINE인 상태에서 (A', B')가 지날 수 있는 경로는 다음과 같이 정해져있습니다. (검은색 실선 상자)

 

검은색 실선 상자의 각 모서리는 다른 좌표들을 참고하여 쉽게 도출할 수 있습니다. POINT 상태가 아니며, (A', B')가 검은 선 위에 있다면 LINE 상태가 되는 것입니다. 

 

 

 

세번째 FACE는 아래 그림과 같은 경우를 포함하여 P와 Q에 겹치는 부분이 있는 경우를 뜻합니다. 따라서 조금만 생각해보면, Q(A', B')의 값은 무조건 ( X’+A’-A , Y’+B’-B )의 좌표값보다 작으며, ( X-(A’-A) , Y- (B’-B) )의 좌표값보다는 크다는 사실을 도출해낼 수 있습니다. 

 

 

 

네 번째 NULL은 P와 Q가 접점을 전혀 공유하지 않는 상태로, 위 세 가지 케이스를 제외한 모든 값입니다. 

 

 

이로서 문제를 해결할 수 있는 모든 재료가 모였습니다. 각 박스의 좌표값의 범위가 -10의 9승에서 10의 9승 사이로, 계산 중 int의 범위를 넘어갈 수도 있음을 주의하며 코드를 작성합니다.

 

 

코드 작성

---

#include <stdio.h>

int main() {
    long long x1, y1, x2, y2; //각 x, y, x', y'
    long long a1, b1, a2, b2; //각 a, b, a', b'
    
    scanf("%lld %lld %lld %lld\n%lld %lld %lld %lld", &x1, &y1, &x2, &y2, &a1, &b1, &a2, &b2);
   // 계산 중 int 범위를 넘길 수도 있으므로 long long 자료형을 사용 
    
    if (
            (a2==x1 && b2==y2+b2-b1) || (a2==x1 && b2==y1) || 
            (a2==x2+a2-a1 && b2==y1) || (a2==x2+a2-a1 && b2==y2+b2-b1)
            // Q의 모서리와 갈색 박스의 모서리 좌표가 같은 지 검사. 같다면 POINT.
    	) printf("POINT"); 
    else if (
            (x1<a2 && a2<x2+a2-a1 && (b2==y2+b2-b1 || b2==y1)) || // Q가 P의 상단 or 하단에 위치한 LINE 상태일 경우
            (y1<b2 && b2<y2+b2-b1 && (a2==x1 || a2==x2+a2-a1)) // Q가 P의 우측 or 좌측에 위치한 LINE 상태일 경우
        ) printf("LINE");
    else if (
            a2<x2+a2-a1 && b2<y2+b2-b1 && x1-(a2-a1)<a1 && y1-(b2-b1)<b1 
            // Q의 (a, b)와 (a', b')가 갈색 박스의 좌측 하단 좌표보다 크고, 우측 상단 좌표보다 작은 지 검사
        ) printf("FACE");
    else printf("NULL"); // 위 케이스에 전부 해당하지 않는다면 NULL
    
    return 0;
}

 

 

END.