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:

• Consider two points A,B in space at locations ( ) and ( ). The separation from A to B can be represented by the vector containing both the direction and the distance as the magnitude of the vector .
• Motion in a two-dimensional plane will have components along both the x-axis and the y-axis. Velocity can thus be described as a vector , where x,y are the speeds along the x-axis and y-axis, respectively. The overall speed is the magnitude of the vector .
• Earth will pull the asteroid towards itself with an attraction g proportional to its mass divided by the square of their distance . The gravitational force will be composed of a vector pointing from the asteroid to Earth such that its magnitude .
• The change in asteroid's velocity can be approximated as , where the t is the amount of time the gravitational force acts on the asteroid. The change in the asteroid's position can be approximated as , where t is the amount of time the asteroid travels with velocity .

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 , resulting in a distance . The gravitational attraction . The gravitation force must point from the asteroid to the earth (i.e., match ) and have a magnitude , 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 , 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 , 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 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 1), you may stop. Otherwise you may output the position calculated up to c calculations.

## Example

Input:

```0 0
0 1
50 5 0
3 15```

Output:

```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

Up: UMD HPC98 Questions Previous: Thread Partitioning

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