백준 15973번: 두 박스

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

15973번: 두 박스

두 사각형 a, b에 대해, a.x1< a.x2, a.y1 < a.y2, b.x1 < b.x2, b.y1 < b.y2 네 식이 모두 조건에 의해 성립한다. 따라서 a.x2 < b.x1, b.x2 < a.x1인 경우 두 사각형은 x축 좌표에 대해 서로 만나지 않고, a.y2 < b.y1, b.y2 < a.y1인 경우 두 사각형은 y축 좌표에 대해 만나지 않는다. 따라서 위 두 경우 사각형은 만나지 않으므로 두 사각형의 교차 관계는 NULL이다.

이제 두 사각형의 다른 위치의 좌표가 같은 값을 지닌 경우를 보자, 즉 a.x2 == b.x1, b.x2 == a.x1, a.y2 == b.y1, b.y2 == a.y1 네 식 중 하나라도 참인 경우를 보자. 우선  네 식 중 하나라도 참이라면 두 사각형의 내부가 겹칠 수 없으므로 이 경우 두 사각형의 위치 관계는 FACE일 수 없다. 즉 네 식 모두 거짓이라면 두 사각형의 위치 관계는 FACE이다. 네 식 중 셋 이상이 참이라면 x와 y 두 좌표 중 적어도 하나는 d < a, b < c이고 a == b < c == d가 되는데, 이 경우 a < d이고 d < a 이므로 모순이므로 그러한 경우는 존재하지 않는다. 네 식 중 하나가 참이라면 변 하나가 맞닿아 있고 관계가 FACE가 아니므로, 두 사각형의 관계는 LINE이고, 네 식 중 둘이 참이라면 POINT를 제외한 그 어떤 경우도 아니므로 두 사각형의 위치 관계는 POINT이다.

#include <cstdio>

class square {
public:
    int x1, y1, x2, y2;
    square() { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); }
};

int main() {
    // 두 사각형의 각 좌표를 클래스 형식으로 저장
    square a, b;
    // 서로 다른 위치의 좌표가 일치하는 가짓수
    int i = (a.x2 == b.x1) + (a.y2 == b.y1) + (b.x2 == a.x1) + (b.y2 == a.y1);

    // x축 좌표 혹은 y축 좌표가 서로 만나지 않는다면 위치 관계는 NULL
    if (a.x2 < b.x1 || b.x2 < a.x1 || a.y2 < b.y1 || b.y2 < a.y1)
        printf("NULL\n");
    // 서로 다른 위치의 좌표가 일치하는 경우가 없다면 위치 관계는 FACE
    else if (!i) printf("FACE\n");
    // 서로 다른 위치의 좌표가 일치하는 경우가 1이라면 LINE, 2라면 POINT
    else printf("%s\n", i == 1 ? "LINE" : "POINT");
    return 0;
}