(Creat de '_domino_':user/domino la data de _2006-01-05_ categoria __, autor(i) _Daniel Pasaila, Mircea Pasoi_)
*Continut scurt:*

 ==Include(page="template/raw")==
 
In acest articol veti gasi solutiile pentru problemele propuse la concursul USACO, editia din luna decembrie 2005, divizia GOLD. Testele si enunturile sunt disponibile la sectiunea Download.

 In acest articol veti gasi solutiile pentru problemele propuse la concursul USACO, editia din luna decembrie 2005, divizia GOLD. Testele si enunturile sunt disponibile la sectiunea Download.

*Continut lung:*

==Include(page="template/raw")==
 

Cow Patterns

Dupa cum au aratat-o si rezultatele, aceasta problema a fost cea mai simpla din concurs. Trebuie sa determinam numarul de dreptunghiuri a caror laturi nu intalnsesc laturile altor dreptunghiuri. De asemenea, sa nu uitam ca dreptunghiurile nu se pot suprapune. In aceste conditii observam ca daca doua dreptunghiuri se intersecteaza atunci se vor intersecta si 2 segmente verticale sau 2 segmente orizontale. Putem astfel sa luam mai intai toate segmentele verticale, vedem care dintre acestea se intersecteaza cu altele si marcam dreptunghiurile lor ca fiind rele. Repetam algoritmul si pentru segmentele orizontale, iar la sfarsit numaram cate dreptunghiuri bune ne-au ramas.

Problema pe care trebuie sa o rezolvam acum este urmatoarea: avand K segmente paralele cu axa Oy trebuie sa determinam care dintre acestea se intersecteaza cu altele. Pentru aceasta sortam segmentele in primul rand dupa coordonata x si in al 2-lea rand dupa coordonata y minima. Dupa aceasta sortare putem determina in O(K) segmentele care se intersecteaza. Parcurgem vectorul de la stanga la dreapta, si pentru fiecare pas vedem daca segmentul curent se intersecteaza cu un segment precedent. Pentru aceasta trebuie sa tinem o variabila ls care reprezinta coordonata y maxima atinsa pana la un moment dat. Pentru segmentul i fie ymin_i, ymax_i si x_i coordonatele lui. Pentru un i daca x_i != x_i*1 sau ymin_i > ls initializam ls cu ymax_i. Altfel marcam segmentul i si segmentul cu care am obtinut maximul ls ca fiind rele, iar ls devine MAX(ls, ymax_i).

Problema pe care trebuie sa o rezolvam acum este urmatoarea: avand K segmente paralele cu axa Oy trebuie sa determinam care dintre acestea se intersecteaza cu altele. Pentru aceasta sortam segmentele in primul rand dupa coordonata x si in al 2-lea rand dupa coordonata y minima. Dupa aceasta sortare putem determina in O(K) segmentele care se intersecteaza. Parcurgem vectorul de la stanga la dreapta, si pentru fiecare pas vedem daca segmentul curent se intersecteaza cu un segment precedent. Pentru aceasta trebuie sa tinem o variabila ls care reprezinta coordonata y maxima atinsa pana la un moment dat. Pentru segmentul i fie ymin_i, ymax_i si x_i coordonatele lui. Pentru un i daca x_i != x_iâ??1 sau ymin_i > ls initializam ls cu ymax_i. Altfel marcam segmentul i si segmentul cu care am obtinut maximul ls ca fiind rele, iar ls devine MAX(ls, ymax_i).

Problema se rezolva similar si pentru segmentele orizontale. Complexitatea algoritmului este O(N logN).