Problem I
Geimskip
Languages
en
is
“A long time ago, in a galaxy far, far away…”
The rebels have finally found the location of the new Death Star and hope to perform an all out attack under the leadership of General Gial Ackbar. Ackbar has committed all of their ships, the ships being MC80 starships, CR90 corvettes, Dornic attack ships, YT-2400 light frigates and various smaller attack ships like T-65B X-wings.
What General Ackbar doesn’t know is that Han Solo and his team died in an unsuccessful attempt to destroy the energy core of the protective shield. Furthermore Admiral Piett has set up a trap so the Empire can be rid of the rebels once and for all. This well planned trap consists of explosives that the admiral has placed at the locations where the rebel fleet comes out of their hyperjumps.
Since General Ackbar had a mild stroke when he discovered the trap, he’s incapable of assessing the damage to the fleet. Can you help him?
Input
The first line of the input contains one integer $N$. On the next $N$ lines thare are descriptions of the ships in the rebel fleet where the $i$-th line contains four integers $x_i,y_i,z_i$ and $r_i$. The first three numbers $(x_i,y_i,z_i)$ denote the position of the $i$-th ship in three-dimensional space and $r_i$ is its explosive radius. Next there is a line containing a single integer $M$. On the next $M$ lines are descriptions of the admiral’s bombs where the $j$-th line contains four integers $x_j,y_j,z_j$ and $r_j$. The first three integers $(x_j,y_j,z_j)$ denote the location of the $j$-th bomb in three-dimensional space and $r_j$ is its explosive radius. You may assume no two ships intersect.
Output
Print a single integer $k$, the number of ships in the rebel sheep that survive the trap.
Explanation of Sample Inputs
The first sample contains one spaceship, located at $(0,0,0)$ and having radius $3$, and two bombs. The first bomb is located at $(2,3-3)$ and has explosive radius $3$. The second bomb is located at $(-2,2,2)$ and has explosive radius $2$. As can be seen on the image the first bomb has no effect on the ship but the second is powerful enough to blow up the spaceship. Thus the output is $0$ since no ship survived.
In the second sample no ships and bombs intersect, so the only ship survives.
In the last input the fourth bomb causes the second ship to explode. That causes a chain reaction making the first ship explode as well, so no ship survives.
Scoring
Group |
Points |
Constraints |
1 |
10 |
$N = 1,\, 0 \leq M \leq 10,\, -100 \leq x_i,y_i,z_i \leq 100,\, 1 \leq r \leq 10$ |
2 |
10 |
$N = 1,\, 0 \leq M \leq 10^3,\, -100 \leq x_i,y_i,z_i \leq 100,\, 1 \leq r \leq 10$ |
3 |
25 |
$0 \leq N,M \leq 10^3,\, -100 \leq x_i,y_i,z_i \leq 100,\, 1 \leq r \leq 10$, no chain reactions |
4 |
25 |
$0 \leq N,M \leq 10^3,\, -100 \leq x_i,y_i,z_i \leq 100,\, 1 \leq r \leq 10$ |
5 |
30 |
$0 \leq N,M \leq 10^3,\, -10^4 \leq x_i,y_i,z_i \leq 10^4,\, 1 \leq r \leq 10^3$ |
Sample Input 1 | Sample Output 1 |
---|---|
1 0 0 0 3 2 2 3 -3 1 -2 2 2 2 |
0 |
Sample Input 2 | Sample Output 2 |
---|---|
1 0 0 0 3 3 2 3 -3 1 -2 2 6 3 1 -5 -2 2 |
1 |
Sample Input 3 | Sample Output 3 |
---|---|
2 0 0 0 3 7 -2 4 4 4 2 3 -3 1 -2 2 6 3 1 -5 -2 2 4 -3 6 2 |
0 |