Rings

Time limit3sMemory limit128 MB

Summary

Decide whether two unit circles in 3D space are linked like chain rings from their centers and orientation vectors.

Level: Medium7 of 10
Topics: Geometry, Math
Solved: No attempts yet

Problem

Two circles of radius 1 lie in 3D space. Circle $i$ is fixed by its centre $c_i = (cx_i, cy_i, cz_i)$ and two orthogonal unit vectors $u_i$ and $v_i$ , and its points are

$\{\, c_i + u_i \cos t + v_i \sin t \;:\; 0 \le t < 2\pi \,\}$

Decide whether the two circles are linked like the rings of a chain. They are linked when no motion pulls them apart without passing one circle through the other.

Input

The first line contains three real numbers $cx_1$ , $cy_1$ , $cz_1$ , the centre of the first circle, with $-3 \le cx_1, cy_1, cz_1 \le 3$ .

The second line contains six real numbers $vx_{1,1}$ , $vy_{1,1}$ , $vz_{1,1}$ , $vx_{1,2}$ , $vy_{1,2}$ , $vz_{1,2}$ , each between $-1$ and $1$ . The first three are the unit vector $u_1$ pointing from the centre to the circumference, and the last three are the unit vector $v_1$ defined the same way. The two vectors are orthogonal.

The third and fourth lines describe the second circle in the same format.

No input has the two circles touching.

Output

Print "YES" if the two circles are linked like the rings of a chain, and "NO" otherwise. Do not print the quotes.

Examples4

Example 1

Input

0.0 0.0 0.0
1.0 0.0 0.0 0.0 1.0 0.0
1.0 0.0 0.5
1.0 0.0 0.0 0.0 0.0 1.0

Expected output

YES

Example 2

Input

0.0 0.0 0.0
1.0 0.0 0.0 0.0 1.0 0.0
0.0 3.0 0.0
0.0 1.0 0.0 -1.0 0.0 0.0

Expected output

NO

Example 3

Input

1.2 2.3 -0.5
1.0 0.0 0.0 0.0 1.0 0.0
1.1 2.3 -0.4
1.0 0.0 0.0 0.0 0.70710678 0.70710678

Expected output

YES

Example 4

Input

1.2 2.3 -0.5
1.0 0.0 0.0 0.0 1.0 0.0
1.1 2.7 -0.1
1.0 0.0 0.0 0.0 0.70710678 0.70710678

Expected output

NO