Programovacia Minisúťaž III.

Zadanie vo formáte PDF si môžete stiahnuť tu.

Zadanie. V rovine je zadané n kruhov (3 ≤ n ≤ 100). Nájdite obvod rovinnej oblasti, ktorá vznikne zjednotením zadaných kruhov. Na nasledujúcich obrázkoch je ten obvod znázornený hrubšími čiarami. V prípade, že tá oblasť je "deravá" (ako na druhom obrázku), do obvodu počítame aj vnútorné oblúky, ktoré vytvárajú "diery".
Desať kruhov Diery
Špecifikácia pre implementáciu riešenia. Riešitelia napíšu program v ľubovoľnom programovacom jazyku. Podmienkou je, aby tento programovací jazyk bol dostupný v bežných distribúciach OS Linux (Debian, Ubuntu, Fedora, OpenSuse,...). Ako riešenie odovzdajú zdrojové kódy programu. Riešitelia uvedú krátky popis algoritmov, ktoré použili, alebo patrične okomentujú zdrojové texty, aby to bolo zrejmé z nich.
Program číta zo štandardného vstupu a výsledky vypisuje na štandardný výstup. Vstup obsahuje niekoľko testovacích prípadov (každý z nich obsahuje horeuvedený konečný počet kruhov). Testovacie prípady sú oddelené prázdnymi riadkami. Riadky, špecifikujúce kruhy majú tvar:    (Sx, Sy) R     kde Sx, Sy su súradnice stredu a R je polomer kruhu. Na počte medzier nezáleží. Napr. pre vyššieuvedený obrázok s tromi kruhmi by vstup mohol mať takéto tri riadky (vo všeobecnosti, súradnice stredu nemusia byť celé čísla):
(5,6) 3.6
(11,4) 3.2
(9,9) 2.4
 Vystupom programu sú vypočítané obvody pre jednotlivé testovanie prípady, každý na osobitnom riadku. Výsledky musia byť vypísané aspoň na 7 desatinných miest, ktoré musia byť správne. Vzorový príklad (malého) vstupu a správneho výstupu bude uverejnený na webovej stránke minusúťaže.
Hodnotenie súťažiacich, ceny. Testovacie dáta budú obsahovať 100 testovacích prípadov. Neprekročiteľný limit na ich vyriešenie je 5 minút, pri jeho prekročení súťažiaci žiadne body neziskáva. Inak, súťažiaci získa toľko bodov, koľko testovacích prípadov vyrieši správne. Pri rovnosti bodov rozhoduje veľkosť priemernej odchýlky od správnych riešení pre všetkých 100 prípadov.
Prví traja súťažiaci budú odmenení skromnými cenami - knihy o OSS softvéri, Numerických metódach a aj (symbolicky :-) finančne: 1. miesto - 20 Euro, 2. miesto - 15 Euro a 3. miesto - 10 Euro. Podľa počtu a úspešnosti súťažiacich, knihy môžu dostať (niektoré v elektronickej podobe) aj ďalší.
Priebeh súťaže. Do súťaže sa môže zapojiť každý, koho zaujme. Ceny dostávajú len študenti základných, stredných a vysokých škôl. Súťaž začína 8. marca 2010 a končí 3. mája 2010 o 1200 hod. Súťažné príspevky (zdrojové texty, vyhovujúce horeuvedenej špecifikácii) je treba odosielať na adresu Michal.Kaukic@fri.uniza.sk.
Je možný ľubovoľný počet pokusov. Po každom odoslanom riešení dostanete oznámenie, koľko prípadov ste správne vyriešili, príp. že ste prekročili časový limit. Je možné, že o toto sa bude starať automatický "sudca", podrobnosti zverejníme na stránke minisúťaže. Testovacia sada pre priebežné oznamy o úspešnosti nebude tá istá, ako sada testovacích prípadov pre konečné hodnotenie. Bude sa hodnotiť riešenie, ktoré súťažiaci pošle najneskôr. V prípade, že dáva horšie výsledky, ako predchádzajúce riešenie, hodnotí sa riešenie predposledné.
Prajem vám pekné zážitky a úspech pri riešení. :-)


Michal Kaukič
V Žiline, 3. marca 2010


File translated from TEX by TTH, version 3.87.
On 3 Mar 2010, 10:57.