Задача №112784. Мосты
Два города в пустыне соединены рекой. Река представляет собой ломаную, с началом в одном городе и с концом в другом. Каждый участок ломаной течет строго с юга на север, т.е. в стороны увеличения y-координаты.
Мэры обоих городов решили построить дорогу, чтобы соединить оба города. Если дорога будет пересекать реку, то в этом месте нужно будет построить мост. Строительство одного метра дороги стоит 1 шиллинг, а один мост стоит T шиллингов. Помогите мэрам найти минимальную стоимость дороги.
Первая строка содержит два числа: целое число N — количество поворотов реки и действительное число 0 ≤ T ≤ 106 — стоимость моста. Следующие N строк содержат целые координаты поворотов реки xi и yi < yi + 1. Никакие 3 соседние точки не лежат на одной прямой. Все координаты по модулю не превосходят 105
Выведите одно действительное число — минимальную стоимость дороги. Ответ считается правильным, если он отличается от правильного не более, чем на 10 - 6
5 1
0 0
-1 2
4 3
-3 4
1 5
6.841619
Подзадача 1.
2 ≤ N ≤ 1500. Оптимальная дорога — прямая линия между двумя городами. Решение оценивается в 11 баллов.
Подзадача 2.
2 ≤ N ≤ 1500. Оптимальная дорога не пересекает реку Решение оценивается в 17 баллов.
Подзадача 3.
2 ≤ N ≤ 500. Решение оценивается в 38 баллов.
Подзадача 4.
2 ≤ N ≤ 1500. Решение оценивается в 34 балла.