This page is still under construction.

Parts of this page are still being built. What you see may change.

Collision of Asteroids

Time limit1sMemory limit16 MB

Summary
Given two moving convex hulls in 3D, decide whether they overlap at some past or future time.
Level

Hard8 of 10

Topics
Geometry, Binary search, Implementation
Solved
No attempts yet

Problem

Predicting the trajectories and collisions of asteroids is routine work at an observatory. Bob has spent many hours observing two asteroids, so he knows their exact shapes and velocities. After a sleepless night, however, he can no longer tell whether the two asteroids are about to collide or whether they are the debris left over from a past collision.

You are given the shapes of two convex asteroids together with their velocities. Determine whether they have collided in the past or will collide in the future — that is, whether the two bodies share at least one common point at some moment in time.

Each asteroid moves along a straight line at a constant velocity. Gravity is negligible because the asteroids are far from every planet. You may assume that the two asteroids do not share any point at the reference time t=0t = 0.

Input

The input consists of two blocks, one per asteroid. Each asteroid is the convex hull of the points given in its block.

A block begins with a line containing an integer nn (3≤n≤50 0003 \le n \le 50\,000), the number of points. Each of the following nn lines contains three integers xx, yy, and 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) describing one point. The points are guaranteed not to be coplanar (there exist four of them that do not lie on a common plane). The block ends with a line containing three integers vxv_x, vyv_y, and 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), the velocity of the asteroid.

Output

Print YES if the asteroids have collided or will collide (they share a common point at some time), and NO otherwise.

Examples4

  1. Example 1

    Input
    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
    Expected output
    YES

  2. Example 2

    Input
    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
    Expected output
    NO

  3. Example 3

    Input
    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
    Expected output
    YES

  4. Example 4

    Input
    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
    Expected output
    NO