CCO '10 P5 - Space Miner

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 1G

Problem type
Canadian Computing Competition: 2010 Stage 2, Day 2, Problem 2

There are M (1 \le M \le 1\,000) planets each with v_i (1 \le v_i \le 10\,000) units of resources and radius r_i (1 \le r_i \le 100).

Starting from (0, 0, 0), you travel in straight lines through N (1 \le N \le 1\,000) waypoints in a specific order.

Whenever you travel within D + r_i (1 \le D \le 50) units from a planet's centre, you can mine the planet using your tractor beam retrieving v_i units of resources. Note that if you are exactly D units from the surface of the planet, you can mine the planet. If your path takes you through a planet, do not worry, since your spaceship can drill through planets, which makes mining even easier. Also note that you cannot mine the same planet on a subsequent visit.

Give the number of minerals that can be mined on your journey.

Hint: you should do all calculations with 64-bit integers.

Input Specification

On the first line of input is the number M, the number of planets. On the next M lines are five integers describing each of the M planets. These integers are x_i\ y_i\ z_i\ v_i\ r_i, where the planet i is at position (x_i, y_i, z_i), (where -1\,000 \le x_i, y_i, z_i \le 1\,000) and this planet has v_i resources and radius r_i. On the next line is the number N, the number of waypoints to pass through. Each of the next N lines contains the position of these waypoints, as three integers x_i\ y_i\ z_i (-1\,000 \le x_i, y_i, z_i \le 1\,000). The last line of input is the number D, the maximum distance from a planet's surface that your ship can be and still mine a planet.

Output Specification

On one line, output the amount of minerals that you can mine on your journey.

Sample Input

3
10 0 0 1 1
0 10 0 2 1
0 0 10 4 1
3
8 0 0
0 7 0
0 0 9
1

Sample Output

5

Comments