Задача E. Поездка на Хэллоуин ≡

Автор:А. Жуплев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Владивостокский программист приглашает коллегу к себе домой в гости на празднование Хэллоуина.

Оба программиста живут за городом. Их дома расположены в точках с координатами (XA; YA) и (XB; YB).

В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами начала (XS; YS) и конца (XE; YE). Дорога является платной: за любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение — не имеет значения) взимается плата в размере CR. Остальная местность занята полями, которые (в связи со скорым Хэллоуином) сплошь засажены тыквами. При движении на автомобиле по полю взимается плата в размере CF за каждый километр пути — ущерб за раздавленные тыквы.

Помогите программисту добраться к другу с минимальными затратами.

Обратите внимание, при сколь угодно малом приближении к дороге плата за въезд на неё не взимается. Смотрите пример №3.

Формат входного файла

Во входном файле содержатся десять целых чисел: XA YA XB YB XS YS XE YE CF CR

Формат выходного файла

Выходной файл должен содержать единственное число — минимальные затраты при перемещении из A в B с абсолютной ошибкой не более 10 − 3.

Ограничения

 − 103 ≤ XA, YA, XB, YB, XS, YS, XE, YE ≤ 103

1 ≤ CF ≤ 103

1 ≤ CR ≤ 106

Дома программистов находятся в разных точках и не находятся на дороге

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1 1 2 2 0 3 3 0 1 1
 
2.414213562373095
2 
1 5 4 0
-2 -2 10 10
1 2
 
7.656854249492381
3 
10 10 25 19
15 13 20 16
1 1000000
 
17.492855684535900
0.135s 0.013s 13