Description

Fish is a fish living in the sea. One day he felt bored and remembered a human game called Puzzle Bobble, so he decided to play a variant named Bubble Fish. Fish is not very clear about the rules of Puzzle Bobble (neither are we), so he adopts his own approximate rules.

Imagine the seabed as a planar region. Its top boundary is at distance $H$ from the launch point, and both the left and right boundaries are at distance $W$ from the launch point.

Initially, there are some bubbles of various colors placed at certain positions within this region, and each bubble has diameter $2$ (bubbles are treated as circles).

If two bubbles of the same color are tangent, we say these two bubbles are adjacent.

If two bubbles of the same color are adjacent, or can be connected through a chain of bubbles of the same color, we say these two bubbles are connected.

For convenience, we define the coordinates of the launch point to be $(0, 0)$. Each time, Fish fires a bubble of a given color from the launch point at a given angle.

If the bubble hits a wall or another bubble (that is, at the first moment it becomes tangent to the wall or another bubble), it stops. If this bubble becomes connected to more than one bubble of the same color (i.e., the connected component of that color including the new bubble has size at least $3$), then all bubbles in that component disappear, and Fish earns a score equal to the square of the number of disappeared bubbles.

Note that initially, even if there is a connected component of size greater than $2$, those bubbles do not disappear. Given the initial configuration of bubbles and, for each shot, the color and the angle (measured counterclockwise from the $+x$-axis), output the final total score. Note that Fish cannot fire the next bubble until the previously fired bubble has stopped.

Input Format

The first line contains two real numbers $W, H$, the boundary distances of the game region, accurate to six decimal places.

The next line contains an integer $n$, the number of initial bubbles.

The following $n$ lines: line $i$ contains two floating-point numbers $x_i$ and $y_i$, the center coordinates of the $i$-th bubble, accurate to eight decimal places, followed by an integer $c_i$, the color of the $i$-th bubble.

The next line contains an integer $q$, the number of fired bubbles. The last $q$ lines: line $i$ contains a floating-point number $a_i$, accurate to two decimal places, the firing angle of the $i$-th bubble, followed by an integer $c_i$, the color of the $i$-th bubble.

The testdata guarantees that all initial bubbles lie within the region. It is guaranteed that at the moment of firing, there is never a bubble parked at the launch position.

Because bubbles float in seawater (and due to floating-point precision), we consider bubbles $a$ and $b$ tangent when $(x_a - x_b)^2 + (y_a - y_b)^2 \le (2 \cdot 1)^2 + 10^{-6}$. The testdata guarantees that initially there are no intersecting bubbles.

Output Format

Output a single line containing one integer, the final total score of Fish.

4.000000 10.000000
5
-2.00000000 9.00000000 3
1.00000000 7.26794919 10
-3.00000000 7.26794919 3
2.00000000 9.00000000 10
0.00000000 9.00000000 10
5
66.60 10
106.20 3
88.20 5
91.80 5
84.60 5

34

Hint

For 30% of the testdata, $1 \le n \le 10$, $1 \le q \le 10$.

For another 50% of the testdata, $1 \le n \le 1000$, $1 \le q \le 1000$.

For the remaining 20% of the testdata, $1 \le n \le 10^5$, $1 \le q \le 10$.

For all testdata, $0 < a_i < 180$, $0 < W, H \le 1000$, $1 \le c_i \le 100$.

Translated by ChatGPT 5