Solved by 344 users: ...
UserDateAttemptTimeCMSC
Vladimir_Sitnikov`15 may 2009`Ruby500.41169
adamant`13 jan 2015`C++1000.01226
adamant`13 jan 2015`C++1100.01226
adamant`13 jan 2015`C++800.01228
fetetriste`27 dec 2008`C++400.01229
adamant`13 jan 2015`C++400.01230
adamant`13 jan 2015`C++500.01230
Philip_PV`30 jul 2008`C++600.01245
WsemirZ`14 jan 2008`Kylix900.01251
Dmitry_Gozman`23 nov 2005`Kylix100.01253
tourist`01 nov 2007`FPC100.01254
Abzal_ktl`25 dec 2007`Kylix100.01261
WsemirZ`14 jan 2008`Kylix500.01261
WsemirZ`14 jan 2008`Kylix600.01264
WsemirZ`14 jan 2008`Kylix700.01264
zloy_mipt`04 may 2008`Kylix1000.01266
zloy_mipt`04 may 2008`Kylix1100.01266
zloy_mipt`04 may 2008`Kylix1200.01266
zloy_mipt`04 may 2008`Kylix900.01268
Igor_Kvasov`07 oct 2003`FPC1?.??270
 C++ 192 FPC 95 C 24 Kylix 23 Java 9 Ruby 2 Python 2
` >  >  >  >  >  >  >  >  >  > `

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

 © acm.mipt DevGroupThe page was generated in 200ms