Indiana Jones
Indiana Jones egy elhagyott romvárosban jár. A háztetők mind megsemmisültek egy
háborúban, a falak egy része még áll.
Rengeteg akna van elásva a földben, ezért csak a megmaradt falszakaszokon
biztonságos járni. Indiana Jonesnak meg kell mentenie egy embert, aki
csapdába esett a városban. Két falszakasz között egy falétra segítségével lehet
átmenni, ha elég hosszú a létra ahhoz, hogy átérjen a két falszakasz között.
A falszakaszok kelet-nyugati vagy észak-déli irányúak, Indiana Jones és a csapdába esett ember kezdetben egy-egy falszakasz tetején van.
Feladat
Az ősi város maradványainak térképét ismerjük, és ki kell számítanunk a legrövidebb
létra hosszát, amivel a küldetés végrehajtható.
Bemenet
Az indiana.be állomány több tesztesetet tartalmaz.
Minden teszteset az falszakaszok $N$ számával kezdődik.
($2\le N \le 1000$)
A következő $N$ sor a falszakaszokat adja meg.
Az első az, ahol Indiana Jones van kezdetben, a második pedig az, ahol
a megmentendő ember várakozik. Minden falszakaszt rárom egész kódol:
$-10000\le X, Y, L \le 10000$.
$X$ és $Y$ a falszakasz végpontja, $L$
pedig a hossza. Pozitív $L$ jelenti a kelet-nyugat irányú,
negatív pedig az észak-dél irányú falakat, utóbbi esetben értelemszerűen az
abszolútérték a hossz.
A bemenet végét egy 0 jelzi.
Kimenet
Az indiana.ki minden sora a egy-egy eset megoldását adja meg
valós számként,
két tízedes pontossággal.
Példa
| indiana.be | indiana.ki |
| 14 1 1 5 6 8 2 7 2 -2 5 3 3 2 5 2 2 3 2 2 3 -2 4 3 -2 0 7 1 1 8 2 3 6 -2 4 7 2 6 6 1 6 6 -2 3 -10 0 20 -5 1 10 50 50 100 0 | 1.41 1.00 |