Drepte3
Dacă avem un algoritm eficient de a găsi intersecţia cu x minim pentru setul nostru de drepte atunci problema este rezolvată, pentru că putem aplica de 4 ori acelaşi algoritm pentru a găsi valorile minime şi maxime pentru x şi y.
Sortăm toate dreptele după ordinea lor pe y dacă ar fi intersectate de o dreaptă verticală cu x-ul foarte mic. Dacă avem două drepte ax + by + c = 0 şi a1x + b1y1 + c1 = 0, avem y = (-ax - c) / b şi y1 = (-a1x - c1) / b1. Dacă x este foarte mic (tinde spre minus infinit) atunci y > y1 dacă -a/b > -a1/b1. După ce avem dreptele în ordine sortată, pentru a determina intersecţia dintre ele cu cel mai mic x, este de ajuns să ne uităm la intersecţiile între drepte consecutive în această ordine.
Astfel, soluţia se reduce la o simplă sortare de pante şi un for pe care facem intersecţii de drepte. Complexitatea soluţiei va fi O(n log n).
