2010 Canadian Computing Competition, Stage 2
Day 2, Problem 2: Space Miner
There are M (1 ≤ M ≤ 1000) planets each with vi (1 ≤ vi ≤ 10000) units of resources and radius ri (1 ≤ ri ≤ 100).
Starting from (0,0,0), you travel in straight lines through N (1 ≤ N ≤ 1000) waypoints in a specific order.
Whenever you travel within D+ri (1 ≤ D ≤ 50) units from a planet's center, you can mine the planet using your tractor beam retrieving vi 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.
Input
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 xiyiziviri, where the planet i is at position (xi,yi,zi), (where -1000 ≤ xi, yi, zi ≤ 1000).
After the M planets, there is line containing the integer N, followed by N lines (each with three integers x, y, and z) describing the points on your route in order.
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
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
All Submissions
Best Solutions
Point Value: 15
Time Limit: 2.00s
Memory Limit: 256M
Added: May 19, 2010
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
After the M planets, there's a line with the integer N, followed by N lines (each with 3 integers, x, y, and z) describing the points on your route in order.