How I Wonder What You Are!

Interview

Time limit1sMemory limit128 MB

Summary
For each dataset, count how many of the given stars fall within the angular radius of at least one of several telescopes all located at the origin.
Level

Easy3 of 10

Topics
Geometry, Brute force, Math
Solved
No attempts yet

Problem

A common childhood question is "How many stars are there in the sky?" Under ideal conditions, nearly eight thousand stars are visible to the naked eye in the northern hemisphere. A good telescope reveals many more, but because its field of view is narrow, you can only see a small patch of sky at a time.

On a planet in a solar system billions of light-years from Earth, children ask their parents the very same question. Their telescopes work like ours, each with a circular field of view, but these aliens have many eyes and can look in many directions at once through many telescopes.

Given the positions of a set of stars, a set of telescopes, and the direction each telescope points, count how many stars can be seen through the telescopes in total.

Input

The input consists of one or more datasets. The number of datasets is fewer than 5050.

The first line of a dataset contains a positive integer nn (1≤n≤5001 \le n \le 500), the number of stars. Each of the next nn lines contains three decimal numbers sxs_x, sys_y, szs_z, the position (sx,sy,sz)(s_x, s_y, s_z) of a star in Euclidean coordinates. You may assume −1000≤sx≤1000-1000 \le s_x \le 1000, −1000≤sy≤1000-1000 \le s_y \le 1000, −1000≤sz≤1000-1000 \le s_z \le 1000, and (sx,sy,sz)≠(0,0,0)(s_x, s_y, s_z) \neq (0, 0, 0).

The next line contains a positive integer mm (1≤m≤501 \le m \le 50), the number of telescopes. Each of the next mm lines contains four decimal numbers txt_x, tyt_y, tzt_z, and ψ\psi, describing one telescope.

Every telescope sits at the origin (0,0,0)(0, 0, 0) (the size of the planet is ignored). The first three numbers give the point (tx,ty,tz)(t_x, t_y, t_z) seen at the center of that telescope's view, i.e. its viewing direction. You may assume −1000≤tx≤1000-1000 \le t_x \le 1000, −1000≤ty≤1000-1000 \le t_y \le 1000, −1000≤tz≤1000-1000 \le t_z \le 1000, and (tx,ty,tz)≠(0,0,0)(t_x, t_y, t_z) \neq (0, 0, 0). The fourth number ψ\psi (0≤ψ≤π/20 \le \psi \le \pi/2) is the angular radius of the telescope's field of view, in radians.

Let θi,j\theta_{i,j} be the angle between the direction of the ii-th star and the center direction of the jj-th telescope, and let ψj\psi_j be the angular radius of the jj-th telescope. The ii-th star is observable through the jj-th telescope if and only if θi,j<ψj\theta_{i,j} < \psi_j. You may assume ∣θi,j−ψj∣>0.00000001|\theta_{i,j} - \psi_j| > 0.00000001 for every pair ii and jj.

Figure 1: The direction and angular radius of a telescope.

The end of the input is indicated by a line containing a single zero.

Output

For each dataset, output a single line containing one integer: the number of stars observable through at least one telescope. The output must contain no other characters. A star seen through more than one telescope must not be counted more than once.

Examples3

  1. Example 1

    Input
    3
    100 0 500
    -500.243 -200.1 -300.5
    0 300 200
    2
    1 1 1 0.65
    -1 0 0 1.57
    3
    1 0 0
    0 1 0
    0 0 1
    4
    1 -1 -1 0.9553
    -1 1 -1 0.9554
    -1 -1 1 0.9553
    -1 1 -1 0.9554
    3
    1 0 0
    0 1 0
    0 0 1
    4
    1 -1 -1 0.9553
    -1 1 -1 0.9553
    -1 -1 1 0.9553
    -1 1 -1 0.9553
    0
    
    Expected output
    2
    1
    0
    
  2. Example 2

    Input
    1
    1 0 0
    1
    1 0 0 0.5
    0
    
    Expected output
    1
    
  3. Example 3

    Input
    1
    1 0 0
    1
    -1 0 0 0.5
    0
    
    Expected output
    0