Online MIPT programming contest | РУССКИЙ |
<PREV Problem: | NEXT> |
< |
---|
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#14 4.5 1 -1 1 1 -1 -1 -1 1 |
Output#14.828 |
Author:
23 september 2003
© acm.mipt DevGroup The page was generated in 190ms |