16135번 - OBB(Oriented bounding box) 서브태스크

안녕! 요즘 2차원 슈팅 게임을 만들고 있는데, 좀 어려운 부분이 생겼어. 플레이어가 적이 쏘는 총알에 맞으면 데미지를 입는 것을 구현하고 싶은데, 혹시 네가 도와줄 수 있니? 히트박스(실제로 두 물체의 충돌이 인식되는 공간)는 얼마든지 회전할 수 있는 직사각형 모양이야.

[분리축 이론]

두 볼록다각형이 겹쳐 있지 않으면, 반드시 두 도형을 분리하는 직선이 존재한다. 또한, 그 직선의 방향으로 투영하면 그림자가 겹치지 않을 것이다. 두 도형이 겹쳐 있다면 어떤 방향으로 투영하더라도 반드시 그림자가 겹친다.

투영은 단위벡터와의 내적을 활용해 보자.

두 직사각형의 중심 사이의 거리 벡터를 \(\vec{d}\)라고 하고,

중심으로부터 한 변의 중점까지의 벡터를 각각 \(\vec{A_1},\vec{A_2},\vec{B_1},\vec{B_2}\)라고 하자. 그림에서

$$ \left| \vec{d} \cdot \vec{u} \right| \ge \left| \vec{A_1} \cdot \vec{u} \right| + \left| \vec{A_2} \cdot \vec{u} \right| + \left| \vec{B_1} \cdot \vec{u} \right| + \left| \vec{B_2} \cdot \vec{u} \right| $$

를 만족하면 그림자가 겹치지 않음이 알려져 있다.

원래 두 도형이 겹쳐 있음을 확인하려면 모든 방향의 \(\vec{u}\)에 대해서 확인해야 하지만, 이 문제에서는 4가지 방향에 대해서만 확인해도 된다. 어떤 방향일지 생각해 보자.

첫 줄에 두 직사각형 A와 B의 모든 꼭짓점의 좌표가 시계방향 또는 반시계방향으로 주어진다. 좌표의 절댓값은 2,000이하이다. 넓이가 0인 직사각형이 주어질 수도 있다.

두 직사각형이 겹치면 1, 겹치지 않으면 0을 출력한다. 자세한 내용은 문제를 참고한다.

• 직사각형의 변이 축과 평행하다.

• 추가 제한 없음