Pagini recente » Cod sursa (job #1719401) | Cod sursa (job #2149177) | Atasamentele paginii Profil elmercer | Cod sursa (job #2957654) | Diferente pentru summer-challenge-2009/solutii/runda-1/drepte3 intre reviziile 1 si 5
Nu exista diferente intre titluri.
Diferente intre continut:
h2(#drepte3). 'Drepte3':problema/drepte3
Drepte3 solution here.
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 $a{~1~}x + b{~1~}y{~1~} + c{~1~} = 0$, avem $y = (-ax - c) / b$ şi $y{~1~} = (-a{~1~}x - c{~1~}) / b{~1~}$. Dacă $x$ este foarte mic (tinde spre minus infinit) atunci $y > y{~1~}$ dacă $-a/b > -a{~1~}/b{~1~}$. 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)$.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.