<ПРЕД Задача:
СЛЕД>
Задачу решили 344 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Граница

Time limit = 5 секунд(ы)

Memory limit = 33000 Kb

Пете необходимо из пункта A попасть в пункт B. Но он хочет использовать случай и заодно заехать в дружественую страну, граница с которой пролегает совсем поблизости.

При этом он хочет, чтобы его путь был как можно короче, покольку времени не так уж и много.

Помогите ему решить эту задачу.

Поезда курсируют между всеми городами.

Вход В первой строчке заданы количество городов N (3 ≤ N ≤ 300). Затем идет действительное число R. Затем идут N строчек с описанием их кординат. В каждой строчке координаты X и Y, разделенные пробелом. Граница с дружественной страной — прямая x = 0. Города A и B — это первые два города. Координата X городов A и B положительна. Один из указанных городов лежит за границей, то есть имеет X < 0. Все координаты — действительные числа по модулю меньше 100000.

Известно, что по крайней мере один путь, удовлетворяющий условиям, существует.

Дороги проведены только между теми городами, между которыми расстояние меньше либо равно R.

Выход Минимальная длина пути. (отличие от правильного ответа не должно превосходить 0.01).

PS: Заметьте, что в принципе Петя может заехать в B а потом за границу, а потом опять в B. Но расположение городов такое, что этого не бывает.

Вход#1
4
4.5
1 -1
1 1
-1 -1
-1 1
Выход#1
4.828


Автор:
Ворожцов Артем
23 сентября 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.236.132.132