## LCC/Moose '19 Contest 4 S3 - TPS

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

The Shinkansen (Japanese bullet train) is testing out a new Train Positioning System (TPS) to have better position and velocity data for their trains. Authorities placed beacons along a straight part of the track which each send out a continuous signal with their beacon ID and a current timestamp. The beacons are synchronized to a central atomic clock. Each second after , the train picks up two of these signals and uses the difference between the current time and the received timestamp to calculate the train’s position.

For example, suppose the train picks up a signal from beacons and with time differences equal to and , where the time difference is the current time (an integer number of seconds) and the timestamp. Then the train is at a distance of from the first beacon and from the second, where is the speed of light. It is possible to determine the position of the train using the positions of the beacons and these two distances.

You have access to the signal data received for each seconds by a single train. Unfortunately, the order of the data has been scrambled and the data is missing the IDs of the beacons, i.e. you only have the timestamps , without knowing at which second the timestamp arrived. If you know the positions of all the beacons and assume that the train moved at a constant integer velocity, can you determine the initial position (at ) and the velocity of the train?

#### Input Specification

The input begins with two integers , the number of beacons and the number of seconds for which you have data. The second line contains integers , the locations of the beacons. The next lines each a real number , one of the timestamps received by the train, accurate to at least fifteen decimal places.

For at least 30% of points, .

#### Output Specification

Output two integers: the initial position of the train (at ) and the velocity of the train. It is guaranteed that a unique solution exists.

#### Sample Input 1

3 3
-5 0 100
0.9999999899930771
0.9999999733148724
1.9999999666435905
2.9999999266158991
2.9999997231418010
1.9999996997923143

#### Sample Output 1

3 7

#### Explanation of Sample Input

The timestamps correspond to distances of 3, 8, 10, 22, 83, and 90.

At , the train must have been at position 3, which is at a distance of 8 from the first beacon and a distance of 3 from the second beacon.

At , the train must have been at position 10, which is at a distance of 10 from the second beacon and a distance of 90 from the third beacon.

At , the train must have been at position 17, which is at a distance of 22 from the first beacon and a distance of 83 from the third beacon.