How I Wonder What You Are!
InterviewTime limit1sMemory limit128 MB
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 .
The first line of a dataset contains a positive integer (), the number of stars. Each of the next lines contains three decimal numbers , , , the position of a star in Euclidean coordinates. You may assume , , , and .
The next line contains a positive integer (), the number of telescopes. Each of the next lines contains four decimal numbers , , , and , describing one telescope.
Every telescope sits at the origin (the size of the planet is ignored). The first three numbers give the point seen at the center of that telescope's view, i.e. its viewing direction. You may assume , , , and . The fourth number () is the angular radius of the telescope's field of view, in radians.
Let be the angle between the direction of the -th star and the center direction of the -th telescope, and let be the angular radius of the -th telescope. The -th star is observable through the -th telescope if and only if . You may assume for every pair and .
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.