1989 ACM East Central Regional Programming Contest

Problem 3: A Particle in a Box

In this problem you will calculate the trajectory of a particle moving inside a rectangular box with a hole inside. The particle is considered to have diameter zero, and bounces off the walls with the angle of incidence equal to the angle of reflection. The trajectory starts from a given point (x, y), and is calculated up through a given number of wall impacts, or until it falls in the hole, whatever happens first. See the figure below.

In this figure, the particle has 4 impacts against the walls, and then falls into the hole.

Input

  1. The number of impacts for which the trajectory is to be calculated;
  2. The dimensions of the box;
  3. The radius and coordinates of the center of the circular hole;
  4. The initial position of the particle;
  5. The initial direction of the particle.
The initial direction of the particle is given as two numbers (c, s), which are the length of the projections of an arrow of length 1 (along the particle's direction of motion) onto the x and y axes. (Equivalently, this is the cosine and sine of the angle measured counterclockwise from the +x direction.) If these projections are in the -x or -y directions, respectively, the numbers are negative. Picture it like this:

Remember that the angle of incidence equals angle of reflection:

You should also handle the case when a particle heads directly into a corner; in that case it bounces right back out along the same line.

In your output, you will be asked to write out a line for each impact on the trajectory, identifying the wall (NORTH, SOUTH, EAST or WEST) at which the impact occured, and the coordinate along the wall at which it occured. You will keep generating these lines until the maximum number of impacts is reached, or until the particle falls into the hole. The particle falls into the hole if its calculated trajectory passes the hole center within a distance less than the radius of the hole. When this happens, you merely print a line saying "falling into hole"; you will not need to calculate the coordinates at which this happens.

A run will consist of several different trajectory calculations, each for different boxes, holes and initial conditions. The first input line for each trajectory will be the maximum number of impacts. If this is zero, it indicates the end of the input data.

Note that there is no time or velocity involved here, so it is best viewed not as a simulation but as a calculation analogous to ray-tracing. (Think of the particle as a photon in a box of mirrors with a black round object inside capable of absorbing the photon.) As such, you calculations of the impact points should try to use as much of the precision of the real data type (in Fortran or Pascal) as possible. Box dimensions will be in the range 50.0 to 150.0. You should print the impact positions in the format "dd.dddd".

Also note: You should not need to call any built-in trigonometric functions (like sine, cosine, tangent, arctangent, and so on), although you are not prohibited from doing so if you wish.

You may assume the input is semantically correct. That is, the initial position of the particle is withing the box but outside the circle, the circle is totally within the box, s2+c2=1, and all radii and dimensions are positive.

Sample Input

12 [ = max number of inputs ]
100.000 60.0000 [ = x, y dimensions of box ]
70.0000 40.0000 10.000 [ = x, y coordinates of circle center; radius ]
14.0000 35.0000 0.600000 0.800000 [ = initial x,y coordinates, c,s angle ]
10 ( same for another trajectory )
92.4321 81.3456
60.2301 61.0021 3.2391
27.0398 22.8801 -0.707107 -0.707107
0 [ end of input file indicator ]

Sample Output

IN 100.0000 BY 60.0000 BOX, WITH HOLE OF RADIUS 10.0000 AT 70.0000 40.0000
STARTING AT COORDINATES 14.0000 35.0000 WITH DIRECTION 0.60000 0.80000
   Impact   1 at NORTH wall, x= 32.7500
   Impact   2 at SOUTH wall, x= 77.7500
   Impact   3 at EAST  wall, y= 29.6667
   Impact   4 at NORTH wall, x= 77.2500
   Falling into hole.
IN 92.4321 BY 81.3456 BOX, WITH HOLE OF RADIUS  3.2391 AT 60.2301 61.0021
STARTING AT COORDINATES 27.0398 22.8801 WITH DIRECTION -0.70711 -0.70711
   Impact   1 at SOUTH wall, x= 4.1597
   Impact   2 at WEST  wall, y= 4.1597
   Falling into hole.