Darts

Interview

Time limit1sMemory limit2048 MB

Summary

Given n darts as rays in 3D, count how many hit the elliptical board centered at the origin with axes h and v.

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

Problem

You have joined a project called 'Flying Projectile Coding', which attempts to create a smart machine learning AI that will throw darts at a slightly modified dart board. Before the live testing of this AI, you have decided to train it in a simulation, because that is much faster and cheaper.

In this project, you are tasked with assessing the AI's performance. Since it is still in the early stages of its development, you only care whether a dart hits the board. For now, assume that gravity is negligible, so darts fly in straight lines.

The board

Input

The first line contains an integer $n$ ( $1 \leq n \leq 10^5$ ), the number of darts thrown.

The next two lines each contain three floating-point numbers. The first line is $(h_1, h_2, h_3)$ and the second line is $(v_1, v_2, v_3)$ , with $-10 \leq h_1, h_2, h_3 \leq 10$ and $-10 \leq v_1, v_2, v_3 \leq 10$ . The dart board is mounted at $(0, 0, 0)$ and is shaped like an ellipse with perpendicular axes $(h_1, h_2, h_3)$ and $(v_1, v_2, v_3)$ .

The next $n$ lines each contain six floating-point numbers $p_1, p_2, p_3, d_1, d_2, d_3$ , with $-100 \leq p_1, p_2, p_3 \leq 100$ and $-10 \leq d_1, d_2, d_3 \leq 10$ . Each line describes a dart thrown from position $(p_1, p_2, p_3)$ in direction $(d_1, d_2, d_3)$ .

Output

Print the number of darts that hit the board.

Examples2

Example 1

Input

3
2.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 2.0 2.0 1.0 4.0
0.0 0.0 -2.0 2.0 1.0 4.0
0.0 0.0 2.0 2.0 0.0 0.0

Expected output

Example 2

Input

6
1.0 1.0 0.0
1.0 -1.0 1.0
0.0 0.0 1.0 0.0 0.0 -1.0
0.0 0.0 1.0 1.0 1.0 0.0
0.0 0.0 1.0 1.0 -1.0 1.0
1.0 -1.0 -1.0 -1.0 1.0 8.0
1.0 -1.0 -1.0 1.0 -1.0 8.0
-1.0 1.0 1.0 1.0 -1.0 -8.0

Expected output