 |
Az I. 214. feladat (2009. május) |
I. 214. Legyen egy négyzetben N darab pontunk valamilyen elrendezésben. Minden pont köré meghatározható egy olyan sokszög, amelynek belső pontjai közelebb vannak a kérdéses ponthoz, mint bármely másik ponthoz. Ezek a sokszögek konvexek és folytonosan töltik ki a négyzetet.
Készítsünk programot, amely egy M×M-es (10
M600) négyzetben véletlenszerűen elhelyez N darab (2M150) pontot, majd határozzuk meg grafikusan a sokszög oldalait, illetve színezzük ki a pontok körüli sokszögeket más-más véletlen színnel. A megjelenítés során a pontokat is rajzoljuk ki.
Lehetséges eredmények:
Beküldendő a program forráskódja (i214.pas, i214.cpp, ...), valamint a program rövid dokumentációja (i214.txt, i214.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.
(10 pont)
A beküldési határidő 2009. június 15-én LEJÁRT.
Minta megoldás:
Englert Péter 12. osztályos (Zalaegerszeg, Zrínyi Miklós Gimnázium) megoldása alapján közöljük.
A négyzet M oldalhosszának, N a pontok számának és a kirajzolás módjának beolvasása után a program véletlenszerű x és y egész koordinátát rendel az (1x,yM) tartományból az N ponthoz (kiemelt pontok).
A KEP tömbben, a négyzet minden pontjához hozzárendeljük annak a kiemelt pontnak az indexét, amelyikhez a legközelebb van (ha többhöz is ugyanolyan közel van, akkor a legkisebb indexűt). A távolságot a megfelelő koordináták különbségeinek négyzetösszegével mérjük; hiszen ennek gyöke Pitagorasz tétele alapján a két pontot összekötő szakasz hossza. Mivel a távolság pozitív érték, ezért a négyzetre emelés nem változtat a sorrendjükön. Az x2 függvény a nemnegatív számokon szigorúan monoton növekvő.
Ha a sokszögek oldalait kívánjuk kirajzolni, akkor a program azokat az (x,y) pontokat rajzolja ki, amelyeknek a 4 közvetlen szomszédja közül legalább egyhez nem ugyanazt a számot rendeltük a KEP változóban (mint az adott ponthoz); vagyis van olyan szomszédja, amelyikhez másik kiemelt pont van legközelebb.
Ha a sokszögeket kiszínezni szeretnénk, akkor a program minden kiemelt ponthoz hozzárendel egy véletlenszerű színt. Utána a KEP tömb alapján minden pontot a hozzá legközelebb álló kiemelt ponthoz tartozó színnel rajzolja ki.
A kiemelt pontok a határvonalak kirajzolása, illetve a színezés után kerülnek megjelenítésre.
Statisztika:
5 dolgozat érkezett. 10 pontot kapott: Balla Attila, Englert Péter, Pap 999 Dávid, Szabó 928 Attila. 1 pontot kapott: 1 versenyző.
A KöMaL 2009. májusi informatika feladatai