<PREV Problem:
NEXT>
Solved by 344 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Trip abroad

Time limit = 5 second(s)

Memory limit = 33000 Kb

Petya has to travel from A to B. And he wants to visit neighbor country, becouse he never was there and he would like to see some sights.

But he has no much time and he desided to choose the shortest path.

Petya has found that train roads are only between towns which stay away no more than distance R.

Please, help him to do it. Positions of all neibor towns are given and there is regular train transport between each two towns. The border is the line x=0.

Input Line 1: N — number of towns. 3 ≤ N ≤ 300.
Line 2: R — real number, maximal length of a road 0 ≤ R ≤ 300.
Line 3: Coordinates of A.
Line 4: Coordinates of B.
Line 5..N+2: Coordinates of other towns.
All coordinates are real numbers from the interval (-100 000, 100000). Coordinate X (the first one) of the towns A and B is positive. There is no towns laying at the border x=0.

At least one way from A to B satisfying above conditions exists.

Output Minimal distance. Error should be less than 0.01.

Input#1
4
4.5
1 -1
1 1
-1 -1
-1 1
Output#1
4.828


Author:

23 september 2003

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 23.20.13.165