아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

소행성의 충돌

시간 제한1초메모리 제한16 MB

요약
3차원에서 각자 일정한 속도로 움직이는 두 볼록 껍질이 어느 시점에든 겹치는지 판정한다.
난이도

어려움10점 중 8점

유형
기하, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

소행성의 궤적과 충돌을 예측하는 일은 천문대 직원에게는 일상적인 업무입니다. Bob은 오랜 시간 동안 두 소행성을 관측하여 각 소행성의 정확한 모양과 속도를 알고 있습니다. 그러나 밤을 새운 탓에, 두 소행성이 앞으로 충돌할 것인지 아니면 이미 과거의 충돌로 생긴 파편인지 판단하지 못하고 있습니다.

두 볼록(convex) 소행성의 모양과 속도가 주어질 때, 두 소행성이 과거에 충돌했거나 앞으로 충돌하는지를 판정하세요. 즉, 어느 시각엔가 두 물체가 적어도 한 점을 공유하는지를 판정하면 됩니다.

각 소행성은 일정한 속도로 직선 운동을 합니다. 소행성은 모든 행성에서 멀리 떨어져 있으므로 중력은 무시합니다. 기준 시각 t=0t = 0 에서는 두 소행성이 어떤 점도 공유하지 않는다고 가정할 수 있습니다.

입력

입력은 두 개의 블록으로 이루어지며, 각 블록은 소행성 하나를 나타냅니다. 각 소행성은 주어진 점들의 볼록 껍질(convex hull)입니다.

한 블록은 점의 개수를 나타내는 정수 nn (3≤n≤50 0003 \le n \le 50\,000) 이 적힌 줄로 시작합니다. 이어지는 nn 개의 줄에는 각각 한 점을 나타내는 세 정수 xx, yy, zz (−1 000 000 000≤x,y,z≤1 000 000 000-1\,000\,000\,000 \le x, y, z \le 1\,000\,000\,000) 가 주어집니다. 주어진 점들은 한 평면 위에 있지 않음이 보장됩니다(한 평면 위에 있지 않은 네 점이 존재합니다). 블록의 마지막 줄에는 소행성의 속도를 나타내는 세 정수 vxv_x, vyv_y, vzv_z (−2 000 000≤vx,vy,vz≤2 000 000-2\,000\,000 \le v_x, v_y, v_z \le 2\,000\,000) 가 주어집니다.

출력

두 소행성이 충돌했거나 충돌할 것이면(어느 시각엔가 한 점을 공유하면) YES 를, 그렇지 않으면 NO 를 출력하세요.

예제4

  1. 예제 1

    입력
    8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
-1 0 0
8
5 0 0
5 0 1
5 1 0
5 1 1
6 0 0
6 0 1
6 1 0
6 1 1
1 0 0
    예상 출력
    YES

  2. 예제 2

    입력
    8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 1 0
8
5 5 5
5 5 6
5 6 5
5 6 6
6 5 5
6 5 6
6 6 5
6 6 6
0 2 0
    예상 출력
    NO

  3. 예제 3

    입력
    8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 0 0
8
10 0 0
10 0 1
10 1 0
10 1 1
11 0 0
11 0 1
11 1 0
11 1 1
-1 0 0
    예상 출력
    YES

  4. 예제 4

    입력
    8
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 0 0
8
10 5 0
10 5 1
10 6 0
10 6 1
11 5 0
11 5 1
11 6 0
11 6 1
-1 0 0
    예상 출력
    NO