(Creat de '_Cosmin_':user/Cosmin la data de _2005-01-13_ categoria _Competitii_, autor(i) _Cosmin_)
*Continut scurt:*

 ==Include(page="template/raw")==
 
Dupa incheierea brusca a concursului Algoritmus, ideile de rezolvare ale rundei 6 nu au mai aparut pe site. In acest articol va voi prezenta ideile de rezolvare la problemele la care eu am realizat solutiile oficiale.

 Dupa incheierea brusca a concursului Algoritmus, ideile de rezolvare ale rundei 6 nu au mai aparut pe site. In acest articol va voi prezenta ideile de rezolvare la problemele la care eu am realizat solutiile oficiale.

*Continut lung:*

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

Problema 1: Suprafata
Pentru a rezolva problema folosim paradigma liniei de baleiere folosita mult in rezolvarea problemelor de geometrie computationala (vezi si articolul arbori de intervale din sectiunea download pt alte exemple de probleme in care se foloseste linia de baleiere). Vom considera ca puncte eveniment toate punctele de intersectie intre oricare doua cercuri si punctele de y maxim si de y minim pentru un cerc. Noi avem nevoie numai de coordonata y a acestor puncte pe care o punem intr-un sir. Sortam acest sir ce are maxim n*(n-1) + 2*n coordonate distincte ( n*(n-1) provin din intersectii a cate doua cercuri iar celelalte 2*n din y-ul maxim si y-ul minim pentru fiecare cerc). Intre doua coordonate Y consecutive din vectorul sortat nu exista nici o intersectie intre cercuri . Intersectia unui cerc cu o banda determinata de Yi si Yi+1 este un fel de trapez curbat pe care ni-l putem imagina ca o paranteza deschisa si una inchisa. Pentru a determina aria intersectiei multimii de cercuri cu banda determinata de Yi