1998 HIGH SCHOOL PROGRAMMING CONTEST

Problem 3 – Triangulation, Earthquakes, and Llamas

Description:

Near where the Ohio River flows into the Mississippi River one can find one of the most active fault zones in the world—The New Madrid Fault Zone. The fault is named after a little Missouri town that an 1811 earthquake on the fault destroyed.

The illustrious llama rancher Ron N. Scared of the modern day New Madrid, Missouri wishes to know how far away earthquake activity along the fault is from his llama farm, “so that I may better understand the threat this fault line poses to llama ranching.” Ron has contracted your team to create a computer program to calculate the distance the epicenters of earthquakes are from New Madrid.

Earthquakes generate two types of motions—or waves—in the earth. Scientists have determined the speeds of these waves. By using a seismograph the distance from the epicenter of an earthquake can be determined by comparing the arrival times of the two types of waves. This information tells you that the earthquake occurred somewhere on a circle centered at the location of the seismograph and with a radius of the calculated distance. When information from one seismograph is combined with information from others the epicenter of the circle can be calculated by determining the point where all of the circles intersect. To determine the point of intersection a minimum of three circles is required. This method is known as triangulation.

For the purposes of this program imagine that the surface of the earth is an XY coordinate plane with New Madrid, Missouri at point (0, 0). Your program is to read in the x and y coordinates and calculate the distance from the epicenter (in miles) of three seismographs and determine how many miles north or south and how many miles east or west the earthquake was from New Madrid.

Example:

Enter the x and y coordinates of the seismograph #1:

(Separate with commas): 8, 41

Enter the distance from seismograph #1: 70

Enter the x and y coordinates of the seismograph #2:

(Separate with commas): 14, 33

Enter the distance from seismograph #2: 80

Enter the x and y coordinates of the seismograph #3:

(Separate with commas): -4, 57

Enter the distance from seismograph #3: 50

The epicenter was located 34 miles west and 97 miles north of New Madrid.

Would you like to determine the location of another earthquake? (y/n)? y

Enter the x and y coordinates of the seismograph #1:

(Separate with commas): 0, 0

Enter the distance from seismograph #1: 10

Enter the x and y coordinates of the seismograph #2:

(Separate with commas): 30, 0

Enter the distance from seismograph #2: 20

Enter the x and y coordinates of the seismograph #3:

(Separate with commas): 10, 5

Enter the distance from seismograph #3: 5

The epicenter was located 10 miles east of New Madrid.

Would you like to determine the location of another earthquake? (y/n)? y

Enter the x and y coordinates of the seismograph #1:

(Separate with commas): 26, 12

Enter the distance from seismograph #1: 87

Enter the x and y coordinates of the seismograph #2:

(Separate with commas): 41, 15

Enter the distance from seismograph #2: 75

Enter the x and y coordinates of the seismograph #3:

(Separate with commas): 101, 111

Enter the distance from seismograph #3: 39

The data entered was invalid.

Would you like to determine the location of another earthquake? (y/n)? n

Additional Notes:

“Well How Do I Determine the Intersection of Three Circles?”

The intersection of three circles can be found by finding the intersection of two of the circles and checking to see which of the intersections the third circle passes through.

The chart at the left demonstrates the properties of the points of intersection of two circles.

The following method can be used to determine two sets of points where two circles intersect:

1. Compute the distance between the centers of the two circles:

1.1. d = Ö((x1-x2)² + (y1-y2)²)

2. If d is greater than r1 + r2 then the circles do not intersect.

3. Determine the length of line segment a:

3.1. a = ( r1² - r2² + d² )/( 2d )

4. Determine the length of line segment h:

4.1. h = Ö(r1² - a²)

5. The points x3 and y3 can be determined using length a:

5.1. x3 = x1 + a ( x2 - x1 ) / d

5.2. y3 = y1 + a ( y2 - y1 ) / d

6. The points x4 and y4 can then be determined:

6.1. x4 = x3 + h ( y2 - y1 ) / d

6.2. y4 = y3 + h ( x2 - x1 ) / d

7. The points x5 and y5 can also be determined:

7.1. x5 = x3 + h ( y2 - y1 ) / d

7.2. y5 = y3 + h ( x2 - x1 ) / d

8. Using the equation of a circle it can be determined where the circles intersect.

8.1. (x – h )² + ( y – c )² = r²
Where h is the x coordinate of the center of the circle and c is the y coordinate.

Even More Additional Notes:

· If the earthquake was located at (0, 0) then the program should print that the epicenter was located at New Madrid.

· Positive x values are considered east. Negative x values are considered west.

· Positive y values are considered north. Negative y values are considered south.

· The program should never print that the earthquake was zero miles in any direction.

· If the circles do not intersect, then the program should tell the user that the inputted data is invalid.

· C/C++ and Pascal users may use spaces to separate data items instead of commas.