h2(#drepte3). 'Drepte3':problema/drepte3

Daca avem un algoritm eficient de a gasi intersectia cu x minim pentru setul nostru de drepte atunci problema este rezolvata, pentru ca putem aplica de 4 ori acelasi algoritm pentru a gasi valorile minime si maxime pentru x si y.

Daca avem un algoritm eficient de a gasi intersectia cu $x$ minim pentru setul nostru de drepte atunci problema este rezolvata, pentru ca putem aplica de $4$ ori acelasi algoritm pentru a gasi valorile minime si maxime pentru $x$ si $y$.

Sortam toate dreptele dupa ordinea lor pe y daca ar fi intersectate de o dreapta verticala cu x-ul foarte mic. Daca avem doua drepte ax + by + c = 0 si a1x + b1y1 + c1 = 0, avem y = (-ax -c) / b si y1 = (-a1x - c1) / b1. Daca x este foarte mic (tinde spre minus infinit) atunci y > y1 daca -a/b > -a1/b1. Dupa ce avem dreptele in ordine sortata, pentru a determina intersectia dintre ele cu cel mai mic x este de ajuns sa ne uitam la intersectiile intre drepte consecutive in aceasta ordine.

Sortam toate dreptele dupa ordinea lor pe y daca ar fi intersectate de o dreapta verticala cu x-ul foarte mic. Daca avem doua drepte $ax + by + c = 0$ si $a1x + b1y1 + c1 = 0$, avem $y = (-ax -c) / b$ si $y1 = (-a1x - c1) / b1$. Daca $x$ este foarte mic (tinde spre minus infinit) atunci $y > y1$ daca $-a/b > -a1/b1$. Dupa ce avem dreptele in ordine sortata, pentru a determina intersectia dintre ele cu cel mai mic $x$ este de ajuns sa ne uitam la intersectiile intre drepte consecutive in aceasta ordine.

Astfel solutia se reduce la o simpla sortare de pante si un for pe care facem intersectii de drepte. Complexitatea solutiei va fi O(n log n).

Astfel solutia se reduce la o simpla sortare de pante si un for pe care facem intersectii de drepte. Complexitatea solutiei va fi $O(n log n)$.