<PREV Problem:
NEXT>
Solved by 344 users: ...
UserDateAttemptTimeCMSC
Vladimir_Sitnikov15 may 2009Ruby500.41169 
adamant13 jan 2015C++1000.01226 
adamant13 jan 2015C++1100.01226 
adamant13 jan 2015C++800.01228 
fetetriste27 dec 2008C++400.01229 
adamant13 jan 2015C++400.01230 
adamant13 jan 2015C++500.01230 
Philip_PV30 jul 2008C++600.01245 
WsemirZ14 jan 2008Kylix900.01251 
Dmitry_Gozman23 nov 2005Kylix100.01253 
tourist01 nov 2007FPC100.01254 
Abzal_ktl25 dec 2007Kylix100.01261 
WsemirZ14 jan 2008Kylix500.01261 
WsemirZ14 jan 2008Kylix600.01264 
WsemirZ14 jan 2008Kylix700.01264 
zloy_mipt04 may 2008Kylix1000.01266 
zloy_mipt04 may 2008Kylix1100.01266 
zloy_mipt04 may 2008Kylix1200.01266 
zloy_mipt04 may 2008Kylix900.01268 
Igor_Kvasov07 oct 2003FPC1?.??270 
Languages
C++
192
FPC
95
C
24
Kylix
23
Java
9
Ruby
2
Python
2
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 = 3.233.215.196