next up previous
Up: UMD HPC98 Questions Previous: Thread Partitioning

Asteroid Tracking

(Basis for J. Robert Dorfman Prize for Numerical Computation)

N-body simulation is an important technique used by scientists and engineers to iteratively compute the motions of a number of interacting objects. Objects may range from stars (galaxy formation) to molecules (chemical reactions). We adapt a similar method to track the path of an asteroid as it approaches Earth.

Panic is spreading in world governments as an asteroid approaches the Earth. Your task is to take the position and velocity of the asteroid, along with the gravitational attraction of the Earth, and compute the course of the asteroid. To refresh your memory, you ask your White House science advisor for a quick physics lesson. The key points of motion in a two-dimensional space are:

To make matters clearer, the science advisor gives you the following example. The asteroid is at position (0,0) traveling with velocity (0,1). The Earth is at position (5,0) with a mass of 50. You now begin your calculations. The asteroid and the Earth are separated by the distance vector tex2html_wrap_inline488 , resulting in a distance tex2html_wrap_inline490 . The gravitational attraction tex2html_wrap_inline492 . The gravitation force tex2html_wrap_inline472 must point from the asteroid to the earth (i.e., match tex2html_wrap_inline496 ) and have a magnitude tex2html_wrap_inline474 , so it is calculated to be (2,0).

Now suppose we decide to simulate the position of the asteroid after 0.2 time units. The change in velocity for the asteroid is tex2html_wrap_inline500 , resulting in the new velocity (0,1)+(0.4,0)=(0.4,1). The change in position for the asteroid (if we use the average of the old and new velocities) is tex2html_wrap_inline504 , resulting in the new position (0,0)+(0.04,0.2)=(0.04,0.2). To continue tracking the asteroid, you simply need to repeat the process.

With the refresher course, you feel confident you can calculate the path of the asteroid as it approaches the earth. If at any point of your calculations you find the distance between the asteroid and Earth is less than or equal to 1, you can output the position and stop, since a collision will occur and further computation is pointless!

Unfortunately, just as you are about to begin, a serious problem arises. Power outages caused by gravitational disturbances from the approaching asteroid have severely limited the computing power you have available. As a result, you can only make a small number of position computations.

The process of tracking the asteroid must thus follow this sequence of steps:

  1. calculate distance and force between asteroid and Earth
  2. choose simulated time interval for next calculation
  3. calculate new position and velocity at end of time interval
  4. repeat steps 1-3 (together comprising one position calculation) until one of
    1. collision (distance tex2html_wrap_inline508 1)
    2. end of simulation
    3. limit on number of calculations reached

You now need to decide how to space out your calculations over the entire span of the simulation to achieve the most precise result. An acceptable approach is to simply spread out your calculations evenly by making the interval between calculations the total simulation time period divided by the number of calculations allowed, but other heuristics may yield more precise answers. No extra position calculations are allowed, even if you do not output their results. Your program will be examined to enforce this restriction.

Remember that the precision of your answer is vital. The world is waiting for your results. Good luck!

Input format

The input consists of four lines. The first line consists of a pair of reals (x,y) marking the position of the asteroid. The second line consists of a pair of reals (x,y) marking the current velocity of the asteroid. The third line consists of an ordered triple of reals (m,x,y) giving m, Earth's mass, and x,y, Earth's location. The fourth line consists of pair of real and integer (t,c), where t is the time period you need to cover in your simulation, and c is the number of times you are allowed to calculate the position and velocity of the asteroid. Any position coordinate x,y may be negative, but all other values are positive.

Output format

The output consists of multiple lines in the same format. On each line, output three reals (t,x,y) presenting the position x,y you computed for the asteroid at time t. The numbers must be output up to three decimal places. If the position indicates a collision has occurred (distance tex2html_wrap_inline508 1), you may stop. Otherwise you may output the position calculated up to c calculations.



0 0
0 1
50 5 0
3 15


0.200    0.040    0.200
0.400    0.161    0.398
0.600    0.364    0.592
0.800    0.655    0.776
1.000    1.042    0.945
1.200    1.538    1.091
1.400    2.166    1.200
1.600    2.963    1.245
1.800    4.006    1.158
2.000    5.480    0.653


Test data used in judging

Input 1 Output 1 Graph 1
Input 2 Output 2 Graph 2
Input 3 Output 3 Graph 3
Input 4 Output 4 Graph 4
Input 5 Output 5 Graph 5
Input 6 Output 6 Graph 6
Input 7 Output 7 Graph 7
Input 8 Output 8 Graph 8
Input 9 Output 9 Graph 9

Our solution

  • Solution
  • Graph utility

    next up previous
    Up: UMD HPC98 Questions Previous: Thread Partitioning

    Chau-Wen Tseng
    Tue Mar 24 16:22:12 EST 1998