Feladat: S.118 Korcsoport: - Nehézségi fok: -
Füzet: 2017/szeptember, 360. oldal  PDF  |  MathML 
Témakör(ök): Nehezebb feladat, Programozás, algoritmusok

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Egy tengeren adott N sziget, melyek kiterjedése elhanyagolható a tenger méreteihez képest. Az i-edik (1iN) sziget helyzetét derékszögű koordináta-rendszerben az (Xi,Yi) egész számpárral adjuk meg (0Xi,Yi10000). Az egyik szigetről egy másik szigetre szeretnénk eljutni. Bármely két sziget között hajóval lehet az utat megtenni. A hajók bármely szigeten tudnak üzemanyagot tankolni, amellyel egy adott távolságig tudnak közlekedni. Keressük meg, hogy mekkora az a legkisebb hatótávolságú hajó, amellyel az utazás a két kiválasztott sziget között biztosítható.
A feladatot megoldó program olvassa be a standard bemenet első sorából N értékét, majd a következő N sorból az Xi, Yi szóközzel elválasztott számokat, végül az utolsó sorból az utazás induló és érkező szigetének sorszámát. A program írja a standard kimenetre a legkisebb hatótávolság öt tizedes jegyre kerekített értékét.
Példa (a sortörést a tömörebb írásmód kedvéért / jellel helyettesítettük):

 
Bemenet   Kimenet   5 / 4 9 / 1 8 / 6 5 / 3 3 / 2 5 / 1 5   3.16228   

 
Értékelés: a megoldás lényegét leíró dokumentáció 1 pontot ér. További 9 pont kapható arra a programra, amely a korlátoknak megfelelő bemenetekre helyes kimenetet ad 1 másodperc futásidő alatt. Részpontszám kapható arra programra, amely csak kisebb N érték esetén ad helyes eredményt 1 másodpercen belül.
Beküldendő egy s118.zip tömörített állományban a megoldást leíró dokumentáció és a program forráskódja.