



			POLIGOANE - SOLUTIE
		       ---------------------

	Se determina ecuatiile dreptelor ce unesc fiecare punct din primul poligon cu fiecare
varf din cel de-al doilea poligon, si se determna intersectiile acestor drepte cu dreptunghiul
( avand in vedere ca o dreapta taie un dreptunghi in 2 puncte, se vor considera doar acele puncte
care se afla de aceeasi parte cu poligonul, fata de poligonul 2(adica mai aproape de punctul
de pe primul poligon, decat de pe cel de-al doilea, puncte care determina dreapta respectiva).
Se realizeaza infasuaratoarea convexa a acestor puncte, plus punctele poligonului I,plus colturile
dreptunghiului care se afla de aceeasi parte cu poligonul I, fata de poligonul II. Mai precis,
pt. a determina care din cele 4 colturi se adauga multimii, se consdiera dreapta determinata
de oricare 2 puncte de intersectie (din cele calculate mai devreme). Se calculeaza semnul semi-
planului care contine poligonul II. Se vor adauga acele colturi ale dreptunghiului care sunt in
semiplanul opus (au semn opus fata de dreapta, decat un varf al poligonului II). Avand in vedere
ca exista n1*n2 puncte de intersectie, complexitatea algoritmului de infasuratoare convexa ar
fi prea mare. De aceea se sorteaza punctele dupa X si dupa Y, si se pastreaza, dintre toate
punctele cu acelasi X si acelasi Y, cele care au cealalta coordonata minima, respectiv maxima.
Poligonul care contine in interiorul sau toate aceste puncte este poligonul-solutie.

VARIANTA: Cand se calculeaza punctele de intersectie, se pastreaza punctele extreme (de o parte
si de alta fata de primul poligon), si apoi se determina poligonul ce contine aceste 2 puncte
extreme si punctele poligonului I, avand inclus in interiorul sau, intreg poligonul I.