5. Otravné farmárčenie

Predstavte si post- a zároveň pred- apokalyptický svet, v ktorom ľudstvo skoro vymrelo od hladu (preto post-) a čoskoro pravdepodobne aj vymrie (preto pred-). Hoci ste špičkoví programátori, musíte proti svojej vôli pracovať v poľnohospodárstve, aby ste mali čo jesť vy, vaše deti a iní príbuzní, nehovoriac o zvyšku ľudstva.

Keďže ľudstvo zanevrelo na vedu, a tak odsúdilo Zem k úplnej záhube, jedinou nádejou na prežitie (okrem pestovania kukurice) je opustenie našej zničenej planéty. Aby sme Zem mohli opustiť, musíme najprv nájsť nejakú inú prívetivú planétu a chceme si byť istí, že bude skutočne obývateľná.

Problémom je, že všetky takéto planéty sú veľmi ďaleko a tak nám naše sondy vedia posielať len veľmi malé množstvo informácií. Mohli by sme sa uchýliť k tomu, že nám sondy budú posielať len akési čísla a písmenká o prívetivosti planét, ale ako sa hovorí: ,,Lepšie raz vidieť, ako stokrát počuť.’’

Čo ak na jednej planéte rastú kokosové palmy, šumí more a príjemne hreje neSlniečko a na druhej rastú kaktusy, šumí piesok a nepríjemne páli obrovská ohnivá guľa a my z oboch planét dostaneme rovnakú správu? To teda nie! Ak raz niekto bude posielať takéto sondy, nedajbože aj s ľudskou posádkou, určite im treba dať aj foťáky a nejak vymyslieť, aby sa dali fotky posielať.

Keďže vás úplne prestalo baviť pestovanie kukurice a zatúžili ste po troške dobrodružstva, na večernej prechádzke lesom ste sa snažili vlámať na oplotený súkromný pozemok. Za trest vás okamžite najali majitelia pozemku a za úlohu vám dali vyriešiť problém vesmírnej komunikácie: Ako posielať čo najkvalitnejšie fotografie v malom množstve dát?

Musíte to vymyslieť rýchlo. Majú vaše deti. A predsa len, je to zábavnejšie ako jazdenie na kombajne.

Úloha

Dostanete čiernobiely obrázok v textovom formáte veľkosti \(w\times h\). Vašou úlohou je skomprimovať obrázok pomocou pár referenčných bodov tak, aby sa čo najviac podobal originálu.

Komprimovaný obrázok pozostáva z najviac \(w+h\) bodov, pričom každý bod je popísaný súradnicami \(x, y\) a intenzitou \(I\).

Pôvodný obrázok sa dekompresiou získa tak, že intenzita referenčných bodov zostane rovnaká a intenzita každého zvyšného pixelu sa vypočíta ako vážený priemer intenzít referenčných bodov, váhovaných prevrátenou hodnotou druhej mocniny vzdialenosti. Teda intenzitu pixela \(x,y\) z referenčnýxh bodov \((x_1,y_1,I_1),\dots,(x_n,y_n,I_n)\) určíme ako: \[I = \frac{\frac{I_1}{dx_1^2 + dy_1^2} + \frac{I_2}{dx_2^2 + dy_2^2} + \dots +\frac{I_n}{dx_n^2 + dy_n^2}} {\frac{1}{dx_1^2 + dy_1^2} + \frac{1}{dx_2^2 + dy_2^2} + \dots +\frac{1}{dx_n^2 + dy_n^2}} \] kde \(dx_i = (x-x_i)\) a \(dy_i = (y-y_i)\).

Obrázky

Stiahni si zip archív z našej stránky. V ňom sa nachádzajú tri cvičné obrázky a 15 súťažných obrázkov. Každý obrázok sa nachádza vo formáte .jpg (klasický JPEG formát) a v takomto formáte .in:

Prvý riadok .in súboru obsahuje dve čísla \(w, h\) (\(1 \leq w,h \leq 500\)) oddelené medzerou – šírku a výšku obrázku.

Nasleduje \(w\times h\) čísel \(p_{i}\), ktoré môžu byť oddelené medzerou, alebo znakom nového riadku. Každé číslo \(0 \leq p_{i} \leq 255\) vyjadruje intenzitu/odtieň sivej pixelu obrázku. Pixely sú zapísané v poradí zľava doprava, zhora dole, teda tak, ako by ste ich normálne čítali.¹

0 je čierna, 255 je biela, čísla medzi určujú svetlejšie a tmavšie odtiene sivej.

Odovzdávanie

Odovzdáva sa zip archív, ktorý obsahuje súbory 01.out, 02.out, atď až po 15.out. Nemusíte odovzdať všetky súbory, body dostanete za tie súbory, ktoré sa v archíve nachádzajú. (Ako obyčajne, do výsledkovky sa počíta len posledný odovzdaný zip archív, takže v ňom je odporúčané mať všetkých 15 súborov). Môžete do archívu pribaliť aj 00.sample.*.out súbory, ale tieto sú len cvičné a nedostanete za ne body.

Každý z odovzdaných súborov musí mať nasledovný formát:

Na prvom riadku sa nachádza číslo \(n \leq w+h\) – počet bodov, ktorými chcete obrázok popísať.

Následne na \(n\) riadkoch sú po 3 čísla oddelené medzerami: \(x, y, I\) – súradnice a intenzity referenčných bodov. Zadané body musia ležať v obrázku, teda \(1 \leq x \leq w, 1 \leq y \leq h\). Intenzity musia byť v rozmedzí od \(0\) po \(255\) vrátane.

Hodnotenie

Každý obrázok sa hodnotí samostatne. Na základe referenčných bodov obrázok dekomprimujeme a porovnáme ho s originálom pixel po pixeli.
Pre obrázok vypočítame strednú kvadratickú odchýlku na základe rozdielov intenzít pixelov, teda sčítame druhé mocniny rozdielov intenzít a na záver výsledok predelíme počtom pixelov obrázku a odmocníme.

Za každý obrázok dostanete nejaký počet bodov od 0 po 1, podľa toho ako malá je vaša kvadratická odchýlka v porovnaní s referenčnou. Ak je vaša odchýlka \(o\) a referenčná odchýlka je \(r\), tak počet bodov, ktoré dostanete bude \(\max(0, min(1, \frac{50+r-o}{50}))^2\), čo v praxi znamená, že plný počet bodov máte ak ste aspoň takí dobrí ako referenčná odchýlka a 0 bodov máte ak ste aspoň o 50 horší. Body, ktoré takto dostanete vám ešte nemusia ostať, zmenia sa, keď sa zmení referenčná odchýlka.

V tejto úlohe budete súťažiť proti sebe, takže referenčná odchýlka sa vypočíta na základe najlepšieho odovzdaného riešenia. Počas behu série budeme odchýlku aktualizovať približne raz za týždeň a po skončení série ju aktualizujeme znova a vypočítame finálne body.

Keďže neodovzdávate programy a nás zaujíma, ako úlohu riešite, môžete k úlohe odovzdať aj popis, kde stručne popíšete, ako ste úlohu riešili a priložíte zdrojové kódy programov, ktoré ste pri riešení použili. Za popis môžete získať 3 body. (Nemusíte odhadovať časovú zložitosť ani dokazovať správnosť riešenia, jednoducho napíšte, čo ste robili.)

Príklady s cvičnými obrázkami

Input:

7 7
255 255 255 255 255 255 255
255 255 0 255 0 255 255
255 255 255 255 255 255 255
255 0 255 255 255 0 255
255 255 0 255 0 255 255
255 255 0 0 0 255 255
255 255 255 255 255 255 255

Output:

9
1 1 255
7 1 255
3 2 0
5 2 0
4 3 255
3 5 0
5 5 0
1 7 255
7 7 255

Stredná kvadratická odchýlka tejto kompresie je 120,597746.

Input:

3 3
255 255 255
255 255 255
255 255 255

Output:

1
2 2 0

Úplne zlá kompresia má kvadratickú odchýlku 255. Ak by sme zmenili zadanú intenzitu na 255, kompresia by bola dokonalá a mala by odchýlku 0.

Na prvom obrázku je originálna fotografia, na druhom môžete vidieť referenčné body, ktorými sa obrázok komprimuje. Na posledom obrázku vidíte, ako by vyzeral obrázok po rekonštrukcii z referenčných bodov. Kvadratická odchýlka tejto kompresie je 49.131287. Vstupný súbor tohto obrázku si viete stiahnuť tu, a výstup našej nedokonalej kompresie tu.