In solutia de la problema forum, autorul calculeaza mai pe lung niste drepte care impart planul in doua semiplane si ar trebui ca punctul nostru sa fie de aceesi parte a acestor drepte ca si punctul (0, 0), ca punctul sa fie bun (adica sa putem pune un forum acolo). Aceste drepte sunt de fapt, mediatoarele despre care vorbiti.
Daca intersectam aceste semiplane, o sa ne dea un poligon in interiorul caruia punctul de query trebuie sa se afle, ca sa fie bun. Ajungem deci la intersectii de semiplane, problema ce se poate rezolva in N log N.
Upper envelope si Lower envelope sunt urmatoarele chestii: impartim dreptele ce determina semiplanele in doua categorii (alea cu panta negativa si alea cu panta pozitiva). Daca intersectam semiplanele dintr-un tip o sa ne dea o structura ori convexa ori concava (un fel de semicerc superior si semicerc inferior (dar mai patratos :
)). Astea se numesc upper envelope si lower envelope pentru ca parca impacheteaza ceva (cred.... nici eu nu stiu de ce le zice asa exact
). Acum punctul nostru trebuie sa fie sub upper envelope si deasupra lui lower envelope ca sa fie bun.
Pentru a determina unul din envelopuri, sortam dreptele dupa panta si iese un algoritm care se foloseste de o stiva. Parcurgem dreptele in ordine si tinem dreptele vizibile (din (0, 0) = origine) intr-o stiva. O dreapta nou bagata o sa faca cateva din ultimele drepte din stiva (posibil) sa nu mai fie vizible, si altfel le scoatem din stiva pe rand. La sfarsit in stiva se vor afla dreptele vizibile din (0, 0). Daca incercati acest algoritm cu toate dreptele odata o sa observati ca nu merge pentru se intampla dubiosenii cand treci la cealata multime de drepte.
Pentru a intelege mai bine algoritmul e bine sa desenati pe foaie cateva drepte de panta de acelasi semn si sa simulati putin, sa vedeti cum se comporta si de ce daca parcurgand dreptele in ordinea pantei, ultimele adaugate pot iesi.
Intersectia celor doua envelopuri ne da fix poligonul care reprezinta intersectia semiplanelor. Intersectia se poate rezolva in complexitate liniara si de aici complexitate de N log N pentru determinarea pligonului (N log N de la sortare).
Sper ca am fost destul de explicit si am lamurit pe toata lumea
Afişează mesaje
