[ RooTeR @ 16.05.2004. 19:24 ] @
I dosao sam (manje vise bez problema) do zadatka Shaping Regions.
Da sumiram problem :
Dat je papir dimenzija a*b,koji je beo (belo=1), i ucitava se n pravougaonika,tako da kad se neki pravougaonik procita (x,y,x1,y1,color), onda se on postavi na taj papir tako da sad taj deo papira na koga smo postavili (to su ucitane koordinate od malopre) ima boju color. Pitanje na kraju je koliko koje boje ima na papiru.

npr :
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

resenje :
1 91
2 84
3 187
4 38


znaci kome nije jasna postavka (verovatno svima ) samo nek nacrtaju primer i sve ce biti jasno. Moja ideja je bila da kako koji podatak ucitam da tako odmah popunjavam matricu integer-a od m[x+1,y+1] do m[x1,y1] i da usput ako na m[k,z] procitam broj c, onda Ukupno[c] smanjim, a Ukupno[color] povecam, i da m[k,z]:=color. To radi za sve osim za poslednji test primer na kome pukne zbog brzine.

Imate li nekih ideja?
[ StMilan @ 16.05.2004. 19:49 ] @
Koja su ogranicenja?

Ako su pravougaonici dosta manji od cele te table onda je bolje da gledas koliko se vidi koji pravougaonik .
[ RooTeR @ 16.05.2004. 21:11 ] @
Mislim da me nisi razumeo.
Ja mogu da stavim neki pravougaonik, pa posle njega jos npr. dva pravougaonika, tako da se od prvog pravougaonika vidi samo neki deo koji nema neki pravilni obli(nije pravougaonik).
[ -zombie- @ 17.05.2004. 00:24 ] @
naravno da je razumeo, nego ti njega nisi..

ako je na papiru već obojen jedan pravougaonik, i treba da obojiš sledeći, može da se desi da se stari i novi preklapaju ili ne. ako se ne preklapaju, nemaš ništa novo da računaš, ali ako se preklapaju, to mogu učiniti na jedan od sledećih šest (opštih) načina, tako da umesto jednog crvenog (starog) pravougaonika, posle farbanja novog imaš od nula do četiri novih:

u prvom slučaju treba samo da smanjiš širinu (desnu koordinatu) starog pravougaonika.

u drugom slučaju, ono vidljivo što je ostalo od starog podeliš na dva pravougaonika (kao što je označeno belom linijom).

u trećem ti novi pravougaonik deli stari na dva. u četvrtom imaš tri, u petom četiri, a u šestom slučaju novi pravougaonik potpuno prekriva stari, tako da ga efektivno briše iz računice.

ponoviš ovaj postupak za svaki novi pravougaonik (tako što ispitaš da li se preklapa sa svakim već postojećim), i na kraju sabereš površine..
[ RooTeR @ 17.05.2004. 14:33 ] @
Da, shvatio sam da je on mene shvatio tek posto sam malo bolje razmislio o tome sta je on napisao ( bio sam jaaakooooo umoran sinoc, tako da mi mozak nije bas nesto funkcionisao ). Hvala na lepim crtezima ! :) (i uopste na odgovoru)
[ RooTeR @ 17.05.2004. 14:57 ] @
Evo, upravo sam poslao resenje na usaco.org, i prosli su mi svih 11 test primera. Ideja koju sam koristio je sledeca: Uz svaku stranicu pravougaonika povuem zamisljenu liniju,i na kraju dobijem mrezu. Za svaku oblast te mreze izracunam boju (pocevsi od poslednjeg ucitanog pravougaonika) i to je to.
Posto nisam bas siguran koliko je ovo jasno sto sam rekao, evo ga kod (ako mene pitate ja mislim da je citko napisan).