banjalukaforum.com

Pozdrav svima!
Posto sam primetio da se ovde jako cesto razmenjuju zadaci sa takmicenja, ja sam nasao isto jedan zadatak, ali zbog svoje karakteristicnosti i brutalne tezine, odlucio sam ga podeliti i sa vama...pa cu prekucat zadatak:

Opis zadatka:

Nekoliko pravougaonih postera, fotografija ili drugih slika su zaleppljeni na zid. Sve njihove strane su vertikalne ili horizontalne. Svaki pravougaonik moze biti delomicno ili potpuno pokriven nekim drugim pravougaonikom. Duzina granicne linije unije svih pravougaonika se naziva obim.
Potrebno je napisati program koji racuna ovaj obim.

Vrhovi svih pravougaonika imaju celobrojne koordinate. Izvrsna verzija Vaseg programa se mora zvati POSTERI.EXE.

Ulazna datoteka:

Ulazni podaci moraju se nalaziti u tekstualnoj datoteci POSTERI.IN. Prva linija datoteke POSTERI.IN sadrzi broj pravougaonika zalepljenih na zid. I svakoj od sledecih linija nalaze se celobrojne (integer) koordinate donje levog i gornjeg levog desno vrha pravougaonika.
Vrednosti ovih koordinata su date kao uredjeni parovi koji se sastoje od x-koordinate iza koje sledi vrednosti y-koordinate.

Izlazna datoteka:

Izlazna datoteka POSTERI.OUT mora sadrzavati samo jedan red sa nenegativnim cijelim brojem koji predstavlja trazeni obim za date šravougaonike.

Vremensko ogranicenje:

Za svaki testni primer program treba da ponudi resenje za najvise 30 sekundi.

Primeri:

POSTERI.IN
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

POSTERI.OUT
228

Napomena:

Broj pravougaonika nije veci od 5000. Sve koordinate su iz intervala [-10000,10000] i svaki dati pravougaonik ima pozitivnu povrsinu, to jest ne moze se svesti na liniju ili tacku. Numericka vrednost moze zahtevati 32-bitnu reprezenzaciju (tip longint odnosno long).

Zadatak trazi da se taj sav "scenarij" odigra u Console, sto dodatno otezava ovu situaciju realizacije programa.

Mislim da je rijesenje jednako zbiru obima svih kvadrata, minus obim kvadrata koji su rezultat presjeka svakog pojedinacnog kvadrata sa ostalim kvadratima. Znaci, za pocetak ti treba jedan objekt koji ce predstavljati x i y koordinate, i duzinu i sirinu kvadrata, jedna funkcija koja kao argument uzima kvadrat, i vraca ti obim kvadrata, jedna funkcija koja prima 2 kvadrata kao argumente, i vraca kvadrat koji je rezultat presjeka ta dva kvadrata. E sad, stvar postaje malo komplikovanija ako se recimo tri kvadrata presijecaju u istoj povrsini, ali mozda ti nesto padne na um.

_________________
You smug-faced crowds with kindling eye
Who cheer when soldier lads march by,
Sneak home and pray you'll never know
The hell where youth and laughter go.

Kako ovo otezava???

30 sec izvrasavanja + 5000 max ulaz = brute force sa malo optimizacije ima da radi vjerovatno.

Posmatraj "poster" kao cetiri linije. Svaki poster(tj linije) uporedi sa svakim posterom. Vidis sta ce se desiti sa tim linijama. Mogu skroz nestati, smanjiti se ili se dobiti dvije manje.

Za optimizaciju: Sortiraj postere prvo po velicini. Pa uporedjuj postere prvo sa vecim tako da se sto manje novih linija stvara i izbaci sve postere koji su sacinjeni u nekim drugim.

Ako sa ovim ne uspijes onda pokusaj sa necim pametnijim. Linije cuvaj u quadtree-u tako da poredjenje sa posterom bude log4(n) maksimalno 7 interacija za pretragu. Sa ovim slozenost je (n^2)*log4(n) sta prolazi sigurno.

_________________
U raju je lijepo, ali u paklu je raja.