Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 1212
Mountain Landscape

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Two seaports at sea level are separated by a mountainous stretch of dry land.

Between the two seaports are N mountain peaks, where N is a positive integer, in the range 1..6.

The N mountain peaks will be denoted by P1,P2,...,PN. The two seaports will be denoted by P0 and PN+1.

The N mountain peaks and the two seaports all lie in the same vertical plane.

The seaport PN+1 is situated directly due east of the seaport P0.

The mountain peaks P1,P2,...,PNare numbered in west-to-east order.

It will be further assumed that neighboring points of this configuration (P0 and P1, P1 and P2, etc.) are in view of each other.

Figure 1 shows an example for the case N = 3:

The Corps of Engineers has been assigned the tasks of determining

the altitudes (elevations above sea level) of the N mountain peaks, and

the length of a straight pipeline which will connect the two seaports.

Figure 2 on the preceding page illustrates the altitudes and pipeline length to be determined.

In order to accomplish their mission, the engineers will take two sets of measurements:

N distance measurements, and

N+1angle of elevation measurements.

Distance measurements:

The straight-line distance between each pair of points (Pk, Pk+1), where k = 0, 1, 2, ..., N-1, is measured. Figure 3 shows the measured distances for the example of Figure 1. (This distance could be measured by actually measuring the time it takes a sound wave to cover the distance.)

Angle of elevation measurements:

For each pair of points (Pk, Pk+1), where k = 0, 1, 2, ..., N, the angle of elevation of Pk+1, viewed from Pk, will be measured; it is the angle formed by a horizontal line and the line segment connecting Pk with Pk+1. Figure 4 on the following page shows the four angles A0, . . ., A 3 to be measured for the example of Figure 1. For sake of clarity, the solid lines (representing the actual mountain landscape) have been removed from Figure 4.

The angles are measured in degrees.

When the point Pk is located at a higher elevation than the point Pk+1, then the angle is negative.

In Figure 4, the angles measured at P0 and P1 are positive, whereas the angles measured at P2 and P3 are negative.

Here is an example of an input:

27.18 705.3 57.76 328.4 -24.3 472 -54.9
45 141 30 200 -40.5 120 21.4 450 -10.3 110.3 28.3 185.2 -60

The number of lines in the input file will be at least 1 but has no upper bound.

Each line of the input file contains data for a self-contained problem of two seaports and N mountain peaks, as previously described.

Each line of input has the format

A0 D0 A1 D1 . . . AN-1 DN-1 AN

The distances Dk and angles A k have been previously defined.

Each distance Dk has at most three digits before the decimal point and at most one digit after the decimal point.

Each angle A k has at most two digits after the decimal point. The fine points of angle measurement and representation have been discussed in previous paragraphs.

All angles are greater than -90 degrees and less than 90 degrees.

The first angle on each line is positive, the last angle on each line is negative.

The maximum number of peaks in a mountain landscape represented by one line of input data is 6, which means 7 angles and 6 distances.

The minimum number of peaks in a mountain landscape represented by one line of input data is 1, which means 2 angles and 1 distance.

The input data listed above will result in the following output:

Problem 6 by team x

Altitude of peak 1 =  322.2
Altitude of peak 2 =  599.9
Altitude of peak 3 =  405.7
Pipeline length    = 1517.9

Altitude of peak 1 =   99.7
Altitude of peak 2 =  199.7
Altitude of peak 3 =  121.8
Altitude of peak 4 =  286.0
Altitude of peak 5 =  266.2
Altitude of peak 6 =  354.0
Pipeline length    = 1259.1
End of problem 6 by team x

For each line of input, the output will consist of:

one blank line;

the altitude of each peak, one peak per line, enumerated in increasing order of peak numbers, in the format shown above;

the length of the pipeline, in the format shown above.

Each altitude, as well as the length of the pipeline, will be displayed rounded to one digit after the decimal point; it will thus consist of at least one but no more than four digits before the decimal point, and exactly one digit following the decimal point.

Observe every detail of the output, such as the exact wording of statements, upper/lower case variations, blank lines and blank spaces.

A few lines of the above output will be reproduced here with a formatting template:

1         2
123456789012345678901234567
Altitude of peak 2 =  599.9
Altitude of peak 3 =  405.7
Pipeline length    = 1517.9

Source: Rocky Mountain 1999
Submit    Status