(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:
)
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
.
,
where x,y are the speeds along the x-axis and y-axis,
respectively. The overall speed is the magnitude of
the vector 
.
.
The gravitational force will be composed of a vector
pointing from the asteroid to Earth
such that its magnitude 
.
, 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)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!
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.
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.
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
