Hide

Problem D
Pop!

A large number of helium balloons have been set up as part of a carnival game. Players shoot a pellet gun into the balloons and earn a point for every balloon they pop. Each balloon is spherical and is tied to a string at the bottom. Each string is taped to a table top at a particular location. Gunshots are described by giving a three-dimensional location, $p$, for the end of the barrel and a vector, $v$, describing the direction the barrel is pointing.

\includegraphics[width=0.3\textwidth ]{balloons.png}

We assume that the pellet is very small and travels in a perfectly straight line when fired. It pops any balloon it passes through. The strings tied to the balloons are so thin that they are never hit by the pellet.

Input

Input contains up to $100$ test cases. Each test case begins with an integer, $1 \le n \le 50$, giving the number of balloons. This is followed by $n$ lines, each containing four space-separated real numbers: the radius of the balloon ($0 \le r \le 10$), the length of string it’s tied to ($0 \le s \le 10$), and the $x$, $y$ location on the table top where the string is taped down ($-10 \le x, y \le 10$).

The balloon descriptions are followed by a line containing an integer $1 \le m \le 10$. The next $m$ lines each contain a gunshot description, which has six space-separated real numbers, the $x$, $y$, $z$ location for $p$ (where $z$ is the height above the table) and the $x$, $y$ and $z$ coordinates for $v$. All shot coordinates are in the range $[-10, 10]$.

You can be assured that the tip of the barrel is not inside any balloon and that no balloons intersect. Also, no string from one balloon touches any other balloon and the direction vector for the gun always has positive length. All real numbers have at most $10$ digits after the decimal point. The end of all test cases is marked by a value of zero for $n$.

Output

For each shot in a test case, output the number of points earned by that shot.

Sample Input 1 Sample Output 1
5
1.0 4.0 0.0 0.0
1.5 3.5 0.0 8.0
1.5 3.5 0.0 -8.0
1.5 3.5 8.0 0.0
1.5 3.5 -8.0 0.0
3
1.0 -10.0 4.5 0 1 0
0.8 -10.0 5.0 0 1 0
-10.0 0.0 5.0 1 0 0
2
1.0 5.0 0.0 10.0
1.0 3.0 0.0 -10.0
1
0.0 0.0 5.0 0.0 1.0 0.1
0
2
1
2
1
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
Author
David Sturgill
Source Baylor Competitive Learning course
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in