Hide

Problem D
Splat

The artist Jackson Pollock used to create works of art by, among other things, dripping paint onto the canvas. He died in 1956, but, if he were alive today, he would probably appreciate some computational help in planning out his masterpieces.

We start with a large, white canvas. We let drops of paint fall onto the canvas one after another, letting each one dry before the next. Thus, successive drops paint over the color left by previous drops. When a drop of paint hits the canvas at point $p$, it spreads out to form a circle of uniform thickness centered at $p$. A drop of volume $v$ will spread out to a circle of radius $r$ where $v = \pi r^2$. Since underlying paint is already dry, all points a distance of $r$ or less from $p$ will be colored with the new drop’s color. Your job is to determine the final color of various points on the painting.

Input

Input begins with an integer $1 \le c \le 100$ indicating the number of painting descriptions which follow. Each painting description starts with an integer $1 \le n \le 100$ giving the number of paint drops that will be applied to the painting. This is followed by $n$ lines, each starting with three real numbers $X$, $Y$, and $V$ and a color. The location $(X, Y)$ is the location of the drop, and $V$ is its paint volume. The color is given as a string with $1$ to $20$ characters (a–z, either case). Each painting description is followed by a series of queries. The query list starts with an integer $1 \le m \le 100$, giving the number of queries. This is followed by $m$ lines, each containing a the $X$ and $Y$ coordinates of the query. All real values are in the range $[0, 1\, 000]$ with at most $3$ digits after the decimal point. All queries fall somewhere on the canvas.

Output

For each query, output the color of the paint at that point on the canvas.

Sample Input 1 Sample Output 1
1
3
0 0 4 blue
2 3 8 red
4 3 10 green
3
1 0
2 2
6 6
blue
red
white

Please log in to submit a solution to this problem

Log in