eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Путь через горы

Путь через горы

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (x_1, y_1), (x_2, y_2), ..., (x_N, y_N), при этом x_i < x_{i+1}. Обычный горный маг находится в точке (x_1, y_1) и очень хочет попасть в точку (x_N, y_N). При этом он может перемещаться только пешком. Он может ходить по поверхности Земли (т.е. вдоль ломаной). А может сотворить в воздухе мост и пройти по нему. Мост может соединять две вершины ломаной: мост не может начинаться и заканчиваться не в вершине ломаной, и мост не может проходить под землей (в т.ч. не может быть туннелем в горе), но мост может каким-то своим участком проходить по поверхности земли. Длина моста не может быть больше R. Суммарно маг может построить не более K мостов. После прохождения моста, он (мост) растворяется в воздухе.

Какое наименьшее расстояние придется пройти магу, чтобы оказаться в точке (x_N, y_N)?

Входные данные

Программа должна прочитать сначала натуральное число N (2N555); затем натуральное число K (1K256) - максимальное количество мостов; далее число R (0R10000) - максимальную возможную длину моста. Далее координаты (x_1, y_1), (x_2, y_2), ..., (x_N, y_N). Все координаты - целые числа, не превышающие по модулю 10000, для всех i от 1 до N-1 выполняется x_{i }< x_{i+1}.

Выходные данные

Программа должна вывести одно число - минимальную длину пути, которую придется пройти магу (как по земле, так и по мостам). Ответ выведите с точностью 6 цифр после десятичной точки.

Пример

Входные данные #1
5 2 5
0 0
2 2
3 -1
4 1
5 0
Выходные данные #1
6.4787086646190746
Автор Илья Порублёв
Источник Летняя школа Севастополь 2013, Волна 1, День 2