Sa pornim de la urmatoarea problema: Avem o colectie de N drepte in plan, oricare doua neconfundate, astfel incat nici una din ele nu trece prin origine. Sa se indice care din drepte sunt vizibile din origine.

Un algoritm decent functioneaza in O(N^2^), astfel: ia fiecare dreapta d~i~, si o intersecteaaza cu fiecare din celelalte drepte d~j~. In acest fel, d~i~ se imparte in doua semidrepte, din care numai una este vizibila din origine, cealalta fiind obturata de catre d~j~. In felul acesta tot intersectam semidrepte peste semidrepte, si vedem daca in final ramanem cu vreun segment vizibil din origine. Desigur, pe parcurs apare tot tacamul de cazuri particulare: drepte verticale, drepte orizontale, erori de calcul, radicali, distante etc. Sper ca v-am scarbit destul ca sa vreti sa aflati si o implementare mai eleganta.

Un algoritm decent functioneaza in O(N^2^), astfel: ia fiecare dreapta d[~i~], si o intersecteaaza cu fiecare din celelalte drepte d[~j~]. In acest fel, d[~i~] se imparte in doua semidrepte, din care numai una este vizibila din origine, cealalta fiind obturata de catre d[~j~]. In felul acesta tot intersectam semidrepte peste semidrepte, si vedem daca in final ramanem cu vreun segment vizibil din origine. Desigur, pe parcurs apare tot tacamul de cazuri particulare: drepte verticale, drepte orizontale, erori de calcul, radicali, distante etc. Sper ca v-am scarbit destul ca sa vreti sa aflati si o implementare mai eleganta.

Vom prezenta un algoritm foarte dragut si foarte cunoscut (in final) care rezolva problema in O(N log N). Facem intai urmatoarea conventie. De vreme ce dreptele nu trec prin origine, ele au ecuatii de forma !voronoi?ec1.bmp!, cu !voronoi?ec2.bmp!. Atunci le vom aduce pe toate la forma !voronoi?img1.bmp! (evident, impartind prin c).

Asta cred ca deja va sugereaza ideea de rezolvare. Daca v-ati gandit la infasuratoare convexa, ati pus punctul pe y. Algoritmul este urmatorul:
* Se da multimea de drepte !voronoi?img14.bmp!

* Aducem toate dreptele la forma !voronoi?img15.bmp!, impartind prin c~i~
* Aflam infasuratoarea convexa a multimii de puncte (a~i~,b~i~)

* Aducem toate dreptele la forma !voronoi?img15.bmp!, impartind prin c[~i]~
* Aflam infasuratoarea convexa a multimii de puncte (a[~i~],b[~i~])

* Punctele de pe aceasta infasuratoare convexa corespund dreptelor vizibile din origine.
De ce asa? Pentru ca punctele de pe infasuratoarea convexa sunt cele mai departate de origine, deci dreptele lor duale sunt cele mai apropiate de origine. Va las placerea de a analiza cazurile particulare, de exemplu cele in care multimea de drepte nu defineste un poligon inchis in jurul originii, ci unul deschis (hint: originea nu apartine infasuratorii convexe a punctelor duale).