Задание 5. Лягушка.
Лягушка мечтает добраться к мухомору. Чтобы это сделать ей надо прыгать по болоту с кочки на кочку. Одним прыжком лягушка может переместиться только до ближайших кочек, которые находятся на расстоянии не более R от текущего местоположения лягушки. Всего на болоте N кочек.
Помогите лягушке добраться до мухомора, так чтобы суммарное расстояние, которое она пропрыгает, было минимально.
Формат входных данных
В первой строке два числа N и R разделенные одним пробелом. Далее следуют N строк с координатами кочек. Каждая строка представляет собой два целых числа (абсцисса и ордината кочки) в диапазоне от 0 до 1000, разделенных одним пробелом. Лягушка находится всегда на первой в списке кочке, а мухомор на последней.
Формат выходных данных
Если решение не существует, то вывести -1. Если решение существует - вывести суммарное расстояние, которое придется напрыгать лягушке, и последовательность координат кочек (координаты каждой кочки на отдельной строке, разделены пробелом), в том порядке, в котором по ним должна прыгать лягушка. Вещественные числа будут сравниваться с точностью до второго знака после запятой.
Примеры
input.txt |
output.txt |
4 3 1 1 1 3 4 1 4 4
|
6.00 1 1 4 1 4 4 |
За полностью сданное задание: 4 балла.
За успешную сдачу до раннего срока (30.11.23 включительно): +2 балла.
- 8 ноября 2022, 19:38
- 14 ноября 2022, 17:16
- 14 ноября 2022, 16:52
- 14 ноября 2022, 16:52
- 13 ноября 2022, 21:18
- 14 ноября 2022, 17:16
- 14 ноября 2022, 16:52
- 14 ноября 2022, 16:52