Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите решить

Соня Мархаева Знаток (259), на голосовании 14 лет назад
.А еще они рассказали князю одну историю (которая, правда, в сказку не вошла...)
Когда корабельщики, распродав товар, собрались возвращаться домой, они обнаружили в трюме корабля похожих на мышей зверушек. Зверушки оказались очень шустрыми (выловить их не удавалось) и едва ли не всеядными - во всяком случае, стенки трюма они уже попытались грызть. Стало понятно, что если они продолжат грызть стенки, то через A дней прогрызут такую дыру, что корабль утонет.
Местные жители рассказали корабельщикам, что вывести зверушек можно с помощью листьев одного растения - стоит разбросать их по трюму, и зверушки сбегут с корабля сами.
Но раздобыть это чудесное растение можно только на одном из дальних островов, до которого еще нужно доплыть.
Однако выяснилось, что грызунам очень нравятся семена одного местного злака, который в больших количествах произрастает на всех окрестных островах. Всего одной единицы веса этих семян хватает зверушкам на целые сутки.
Корабельщики подумали и все же отправились в путешествие за листьями чудесного растения, решив, что по дороге (карта у них имеется) им встретится довольно много островов, где можно будет пополнять запасы семян (чтобы зверушки все же не прогрызли дыру). Запасы семян на островах считаются неограниченными - т.е. корабельщики могут взять с собой столько семян, сколько пожелают (лишь бы было место, куда их погрузить).
Ремонтировать корабль на островах нет технической возможности. Если запасы семян оказались исчерпанными, зверушки принимаются грызть стены трюма, пока им не предоставят любимую еду.

Ваша задача - определить, каков должен быть минимальный объем свободного пространства в трюме, чтобы корабельщики благополучно доплыли до острова с чудесным растением.

Формат входного файла input.txt
Первая строка - целые числа N и A, и V (2 <= N <= 10, 0 <= A <= 1000, 1 <= V <= 10) - количество островов на карте корабельщиков, количество дней, за которое зверушки приведут корабль в негодность и скорость движения корабля.
Далее следуют N строк, каждая из которых содержит пару целых чисел - координаты очередного острова.
Корабль в начале путешествия находится возле острова номер 1, чудесное растение произрастает на острове номер N.

Формат выходного файла output.txt
Первая строка - вещественное число - минимальный объем свободного пространства в трюме, при котором корабельщики доберутся до острова с чудесным растением, с точностью до 10^-5

Пример входного файла - 1
3 0 1
0 0
1 0
4 4

Пример выходного файла - 1
5

Пример входного файла - 2
3 1 1
0 0
5 0
8 4

Пример выходного файла - 2
4.5
Голосование за лучший ответ
Роман Мыслитель (8136) 14 лет назад
вот это грузилово, даже не читал :-D
Похожие вопросы