Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Олимпиадные задачи на английском языке

03/07/2008 | Лето 2008 дорешивание (10I) |

23/07/2008 | Лето 2008 - 10 (I) |

*Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

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 contains integers `Y`, `M`, `N`,
followed by `N` pairs of integers `x_i\ y_i` – hummock coordinates.
The swamp edge Ivan stands on coincides with `y\ =\ 0` line,
and the opposite edge – with `y\ =\ Y` line.

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`.

`1\ ≤\ N\ ≤\ 100`, `1\ ≤\ Y,\ M\ ≤\ 1000`, `0\ ≤\ x_i,\ y_i\ ≤\ 1000`

Sample Input 1

13 7 6 13 3 13 5 9 7 7 7 3 8 2 9

Sample Output 1

20.595

Sample Input 2

20 16 1 100 10

Sample Output 2

-1