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.
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.
On one line, output the amount of minerals that you can mine on your journey.
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