 |
Az S. 118. feladat (2017. szeptember) |
S. 118. Egy tengeren adott \(\displaystyle N\) sziget, melyek kiterjedése elhanyagolható a tenger méreteihez képest. Az \(\displaystyle i\)-edik \(\displaystyle (1 \le i \le N)\) sziget helyzetét derékszögű koordináta-rendszerben az \(\displaystyle (X_i, Y_i)\) egész számpárral adjuk meg \(\displaystyle (0 \le X_i, Y_i \le 10\,000)\). 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 \(\displaystyle N\) értékét \(\displaystyle (N \le 1\,000)\) , majd a következő \(\displaystyle N\) sorból az \(\displaystyle X_i\), \(\displaystyle Y_i\) 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:
| 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 \(\displaystyle 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.
(10 pont)
A beküldési határidő 2017. október 10-én LEJÁRT.
Mintamegoldásként Noszály Áron debreceni, 10. osztályos versenyző (s118na.pdf,s118na.cpp), valamint Gáspár Attila miskolci, 12-edik diák (s118ga.cpp), és Szinyéri Bence nagykanizsai, 12. évfolyamos tanuló (s1118szb.cpp) munkáit adjuk közre.
Tesztállományok és helyes kimenet: teszt.zip
Statisztika:
24 dolgozat érkezett. 10 pontot kapott: Busa 423 Máté, Csertán András, Gáspár Attila, Horcsin Bálint, Horváth 546 János, Horváth Hilda Abigél, Janzer Orsolya Lili, Kiss Gergely, Nagy Nándor, Noszály Áron, Pituk Gábor, Szinyéri 427 Bence, Tóth 827 Balázs, Tran 444 Ádám. 9 pontot kapott: Horváth Botond István, Vári-Kakas Andor. 6 pontot kapott: 2 versenyző. 5 pontot kapott: 1 versenyző. 4 pontot kapott: 2 versenyző. 3 pontot kapott: 2 versenyző. 1 pontot kapott: 1 versenyző.
A KöMaL 2017. szeptemberi informatika feladatai