[C/C++] 백준 #2527 직사각형(수학)

도형에서 위치를 가지고 겹침 판정을 하는 것은 꽤 어려운 일입니다.  이러한 겹침판정은 게임 등에서 충돌이 발생했는지 판정하기 위해서 많이 사용됩니다.  그 중 가장 간단한 판정법은 구(또는 원) 판정입니다.  구 판정법은 두 중심의 거리와 반지름의 합으로 손쉽게 판정을 할 수 있습니다.  다음으로 간단한 것이 축에 평행한 직육면체(또는 직사각형) 판정입니다.  이러한 판정법은 AABB(Axis Aligned Bounding Box)라고 해서 경계 박스 충돌 검사에서 많이 활용됩니다.  이번 문제는 2차원 평면에서 직사각형 충돌 판정을 하는 문제입니다.

 

2D game collision box

 

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

2527번: 직사각형

 

축에 평행한 것이기 때문에 X 축과 Y 축별로 상태를 만들고, 그 상태를 결합해서 판단을 합니다.  X 축으로 투영된 것에는 3개의 상태가 존재합니다.  첫번째는 서로 떨어져 있는 경우입니다.  두번째는 한점에서 만나는 경우입니다.  세번째는 서로 겹쳐 있는 상태입니다.  Y축도 마찬가지로 3가지 상태가 존재합니다.  이것을 표로 만들면 다음과 같습니다.

 

X      Y	split	point	overlap
split	d	d	d
point	d	c	b
overlap	d	b	a

 

총 9개의 상태로 표시했지만, 전 두개의 상태를 OR시켜서 처리했습니다.  그러면 총 6가지의 상태가 나옵니다.

1) d : split and split

2) c : point and point 

3) d : split and point

4) a : overlap and overlap

5) d : overlap and split

6) b : point and overlap

 

이것을 이용해서 프로그램을 하면 다음과 같습니다.

//------------------------------------------
//    baekjoon #2527
//        - by Aubrey Choi
//        - created at 2019-08-29
//------------------------------------------
#include <stdio.h>

int check(int x1, int x2, int x3, int x4)
{
    if(x2<x3 || x1>x4) return 1;
    if(x2==x3 || x1==x4) return 2;
    return 4;
}

int main()
{
    const char *s = "xdcdadb";
    int x1, y1, p1, q1, x2, y2, p2, q2;
    for(int i=0;i<4;i++)
    {
        scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&p1,&q1,&x2,&y2,&p2,&q2);
        printf("%c\n", s[check(x1,p1,x2,p2)|check(y1,q1,y2,q2)]);
    }
}