Observam cu rosu dreptele care delimiteaza fasiile verticale. De asemenea vedem ca punctul $P{~6~}$ are in fasia lui 2 laturi cu y-ul mai mic ca al lui si este in afara poligonului, spre deosebire de punctul $P{~7~}$ care are o singura latura cu y-ul mai mic ca al sau si este in interior.
Avantajul acestei metode este ca functioneaza si in cazul poligoanelor concave, insa are dezavantajul faptului ca pot exista interogari in care punctele sa se afle pe dreapta care delimiteaza fasiile. Practic aceasta metoda este echivalenta cu metoda explicata mai sus, pentru a verifica daca un punct se afla sau nu in interiorul unui poligon oarecare.

In cazul poligoanelor convexe complexitatea este aceeasi ca si la metoda de mai sus, insa in cazul poligoanelor concave complexitatea teoretica e O(N^2 log N + M log N). Acest algoritm poate fi aplicat in rezolvarea problemei 'poligon':http://infoarena.ro/problema/poligon din arhiva de probleme.
 
 

In cazul poligoanelor convexe complexitatea este aceeasi ca si la metoda de mai sus, insa in cazul poligoanelor concave complexitatea teoretica e O(N^2 log N + M log N).

*devilkind* uitativa putin la solutia asta ptr ca nu sunt foarte sigur pe complexitati - in special cand e vb de poligoane concave. Mie mi se pare ca aia e complexitatea insa e posibil sa ma insel

*cotizo* da e corect - asta e si rezolvarea problemei "poligon"

h1. TODO

sugestii de probleme de adaugat
punct in poligon:

  - punct in triunghi [ok]
  - punct in poligon oarecare [ok]
  - punct in poligon convex 2 solutii cautare binara dupa unghi sau dupa y [ok]
  - punct in poligon stelat [ce e poligon stelat?]
  - problema poligon din arhiva [ok, cred]

  - punct in triunghi
  - punct in poligon oarecare
  - punct in poligon convex 2 solutii cautare binara dupa unghi sau dupa y
  - punct in poligon stelat
  - problema poligon din arhiva

infasuratoare convexa - DONE
  vreo 5 metode