Problem F. Frogless swamp ≡
| Author: | D. Vikharev | Time limit: | 2 sec | |
| Input file: | input.txt | Memory limit: | 64 Mb | |
| Output file: | output.txt |
Statement
As is customary, Ivan has shot an arrow to hit a potential bride. He did not know the local swamp was not inhabited by frogs — neither regular nor princess ones. Anyway, the arrow did not fall into the swamp, but flew over to the other side. To retrieve it Ivan has to cross the swamp.
The swamp is a strip of width Y stretching indefinitely both to the east and to the west. Ivan stands at the southern border of the swamp, and wants to get to the northern border. Ivan has a map showing N hummocks capable of holding his weight.
Hummocks are too far from each other to jump,
so Ivan has found a plank of length M to use as a bridge.
Hummocks are also too slippery to stand on, so Ivan decided to
break a plank in two parts (of lengths L and M − L)
and use them to move in the following way:
he would stand on first part, throw the second part over to the nearby hummock,
step onto the second part, pick up the first part,
walk with it across the second one. Repeating this procedure as necessary,
Ivan hopes to reach the other side of the swamp as fast as possible.
Ivan can choose any value of L such that 0 < L < M. Important condition is that Ivan must always stand on the plank. He can, however, put both parts of the plank between the same two hummocks and/or use the parts in any order he wants (for example, put part 1 between hummocks A and B, move to hummock B, put part 2 between hummocks B and C, step onto part 2 staying at hummock B, pick part 1 and put it between B and D, move to hummock D taking part 2 with him).
Your program will be given the swamp width, plank length and hummocks coordinates. It must calculate the shortest distance Ivan has to walk to cross the swamp or determine that he can not do so. Distance is measured from hummock to hummock, even if plank part is longer than the distance between hummocks.
Input file format
Input contains integers Y M N, followed by N pairs of integers xi yi — hummock coordinates. The swamp edge Ivan stands on coincides with y = 0 line, and the opposite edge — with y = Y line.Output file format
Output must contain a single floating point number — the shortest distance Ivan has to travel with at least 3 correct decimal digits. If there is no solution, output must contain the number − 1. An image below illustrates a solution to the first sample.
Constraints
1 ≤ N ≤ 100, 1 ≤ Y, M ≤ 1000, 0 ≤ xi, yi ≤ 1000
Sample tests
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|