시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.3 초 (추가 시간 없음) 32 MB 66 13 11 64.706%

문제

안녕! 요즘 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이하이다.

출력

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

서브태스크 1 (15점)

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

서브태스크 2 (85점)

  • 추가 제한 없음

예제 입력 1

0 0 0 1 1 1 1 0
2 1 3 2 2 3 1 2

예제 출력 1

0

예제 입력 2

1 1 1 -1 -1 -1 -1 1
0 2 -2 0 0 -2 2 0

예제 출력 2

1

노트

넓이가 0인 직사각형이 주어질 수도 있다.

출처

High School > 서울과학고등학교 > SciOI 2018_01 F번

  • 빠진 조건을 찾은 사람: dotorya
  • 문제를 만든 사람: oh040411

채점

  • 예제는 채점하지 않는다.