[C++]백준 - 15973번 문제

15973번: 두 박스 (acmicpc.net)

15973번: 두 박스

 

15973번 : 두 박스

---

2차원 좌표 평면 위에 두 개의 박스(직사각형) P, Q가 놓여 있다. 각 박스의 변은 x축이나 y축에 평행하다. 박스를 연구하는 학수는 이 두 박스의 교차 상태를 파악하여 내부가 겹쳐 있는지 (FACE), 그렇지 않고 선분에서 만나는 지(LINE), 그렇지 않고 한 점에서 만나는지(POINT), 아예 만나지 않는지 (NULL) 구별하려고 한다.

다음 그림은 두 박스의 여러 가지 교차 상태의 예를 보여준다.

 

 

FACE인 경우에는 (d)처럼 어느 한 박스가 다른 박스에 포함될 수도 있다는 점에 유의해야 한다.

두 박스의 정보가 주어졌을 때, 두 박스의 교차 상태를 출력하는 프로그램을 작성하시오.

 

입력

---

표준 입력으로 두 박스의 정보가 한 줄에 하나씩 주어진다. 각 박스의 정보는 왼쪽 아래 꼭짓점 좌표 (x1, y1)과 오른쪽 위 꼭짓점 좌표 (x2, y2)로 구성되는데 이들 좌푯값 x1, y1, x2, y2 (x1 < x2, y1 < y2)가 공백을 사이에 두고 주어진다.

 

모든 서브태스크에서 x좌표와 y좌표는 모두 -109 이상 109 이하인 정수이다.

 

 

출력

---

표준 출력으로 두 박스의 교차 상태를 POINT, LINE, FACE, NULL 중의 하나로 출력한다. 두 박스의 교차 상태는 모두 대문자로 출력한다.

 

 

---

 

생각해 볼 점

---

회전각이 같은(회전하지 않은) 사각형 끼리의 충돌 검증에는

 

AABB 충돌 검사가 있습니다.

 

충돌감지 처리기법 ~ 전체 : 네이버 블로그 (naver.com)

충돌감지 처리기법 ~ 전체

 

AABB 충돌 처리를 응용해서, 한 점이나 한 선에서 만나는 경우도 검증해봅시다.

 

일단 AABB 충돌 처리에서는 4가지를 검사합니다.

 

두 사각형을 임의로 A와 B라고 두었을 때,

 

1. A.Left <= B.Right

2. B.Left <= A.Right

3. A.Bottom <= B.Top

4. B.Bottom <= A.Top

 

이 4가지를 모두 만족하면 만나거나 충돌합니다.

 

이 때, A.Left == B.Right와 같이 "=="인 경우가 나오면 충돌하는게 아니라 만납니다.

 

따라서, 다음과 같이 정리할 수 있습니다.

 

1. NULL = 4가지 중 하나라도 만족하지 않을경우

2. LINE = 4가지 모두 만족하는데, "=="인 경우가 1개인 경우

3. POINT = 4가지 모두 만족하는데, "=="인 경우가 2개인 경우

4. FACE = 4가지 모두 만족하는데, "=="인 경우가 0개인 경우

 

 

코드

---

#include <iostream>
#define POINT pair<int, int>
#define X first
#define Y second
using namespace std;

class RECT
{
private:
	POINT min, max;
public:
	RECT() = default;
	RECT(int const x1, int const y1, int const x2, int const y2) : min{ x1, y1 }, max{ x2, y2 } {}
	void judge(RECT const &other);
};

void RECT::judge(RECT const& other)
{
	//AABB 충돌 판정
	int judging[4] = {	min.X - other.max.X,
						min.Y - other.max.Y,
						other.min.X - max.X,
						other.min.Y - max.Y };

	int summ = 0;
	//케이스 정규화
	for (int i = 0; i < 4; i++)
	{
		if (judging[i] < 0) judging[i] = -1;
		else if (judging[i] == 0) continue;
		else
		{
			//부딪히지 않았으므로 종료
			printf("NULL");
			return;
		}
		summ += judging[i];
	}

	if (summ == -2) printf("POINT");
	else if (summ == -3) printf("LINE");
	else printf("FACE");
}

int main()
{
	RECT A, B;
	
	int x1, x2, y1, y2;
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	A = RECT{ x1, y1, x2, y2 };
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	B = RECT{ x1, y1, x2, y2 };

	A.judge(B);
	return 0;
}

 

그 외

---