Canadian Computing Competition: 2010 Stage 2, Day 2, Problem 2
There are planets each with units of resources and radius .
Starting from , you travel in straight lines through waypoints in a specific order.
Whenever you travel within units from a planet's centre, you can mine the planet using your tractor beam retrieving units of resources. Note that if you are exactly 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 , the number of planets. On the next lines are five integers describing each of the planets. These integers are , where the planet is at position , (where ) and this planet has resources and radius . On the next line is the number , the number of waypoints to pass through. Each of the next lines contains the position of these waypoints, as three integers . The last line of input is the number , 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
Might save you from solving 3 system equations: https://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html