Hide

Problem J
Hitting the Targets

A fundamental operation in computational geometry is determining whether two objects touch. For example, in a game that involves shooting, we want to determine if a player’s shot hits a target. A shot is a two dimensional point, and a target is a two dimensional enclosed area. A shot hits a target if it is inside the target. The boundary of a target is inside the target. Since it is possible for targets to overlap, we want to identify how many targets a shot hits.

\includegraphics[width=0.4\textwidth ]{sampleImage}

The figure above illustrates the targets (large unfilled rectangles and circles) and shots (filled circles) of the sample input. The origin $(0, 0)$ is indicated by a small unfilled circle near the center.

Input

Input starts with an integer $1 \leq m \leq 30$ indicating the number of targets. Each of the next $m$ lines begins with the word rectangle or circle and then a description of the target boundary. A rectangular target’s boundary is given as four integers $x_1~ y_1~ x_2~ y_2$, where $x_1<x_2$ and $y_1<y_2$. The points $(x_1,y_1)$ and $(x_2,y_2)$ are the bottom-left and top-right corners of the rectangle, respectively. A circular target’s boundary is given as three integers $x~ y~ r$. The center of the circle is at $(x,y)$ and the $0<r\leq 1\, 000$ is the radius of the circle.

After the target descriptions is an integer $1 \leq n \leq 100$ indicating the number of shots that follow. The next $n$ lines each contain two integers $x~ y$, indicating the coordinates of a shot. All $x$ and $y$ coordinates for targets and shots are in the range $[-1\, 000,1\, 000]$.

Output

For each of the $n$ shots, print the total number of targets the shot hits.

Sample Input 1 Sample Output 1
3
rectangle 1 1 10 5
circle 5 0 8
rectangle -5 3 5 8
5
1 1
4 5
10 10
-10 -1
4 -3
2
3
0
0
1

Please log in to submit a solution to this problem

Log in