h3. {+Punct in interiorul unui triunghi+}
Se da un triunghi prin coordonatele varfurilor. Se cere sa se afiseze pentru un set de $N$ puncte din plan daca apartin sau nu interiorului triunghiului. Pentru a rezolva aceasta problema, sa consideram triunghiul $ABC$ si punctul $P$, interior acestuia.

!http://infoarena.ro/notiuni-de-geometrie-si-aplicatii?action=download&file=triunghi.jpg!

!notiuni-de-geometrie-si-aplicatii?action=download&file=triunghi.jpg!

Observam ca vectorii ( **AB**, **BP** ), ( **BC**, **CP** ), ( **CA**, **AP** ) vor realiza mereu acelasi tip de intoarcere (in acest caz spre stanga). De aceea, determinantii:

Se va trasa o semidreapta orizontala cu originea in punctul $P$. Daca aceasta semidreapta intersecteaza un numar impar de muchii ale poligonului, atunci punctul se afla in interiorul acestuia. Mentionam ca trebuie avut in vedere cazul in care semidreapta trece chiar printr-un varf de poligon (capat a doua muchii). Vom considera imaginea urmatoare:

 !http://infoarena.ro/notiuni-de-geometrie-si-aplicatii?action=download&file=poligon-raza.jpg!

 !notiuni-de-geometrie-si-aplicatii?action=download&file=poligon-raza.jpg!

In cazul punctului P{~1~}, respectiv P{~2~}, semidreptele intersecteaza 3, respectiv 1 latura (numere impare) deci punctele se afla in interior. Semidreapta corespunzatoare lui P{~3~} intersecteaza o latura si un varf de poligon. Pentru a rezolva acum aceasta problema, o solutie ar fi ca in loc sa alegem semidreapta orizontala, sa luam o semidreapta random, astfel posibilitatea ca ea sa intersecteze varfurile poligonului tinde spre 0. O alta solutie posibila - si mai usor de implementat - este sa consideram ca facand parte dintr-o latura doar punctul cu coordonata y mai mare. Se garanteaza astfel ca laturile care contin punctul de pe semidreapta vor fi numarate de numar par de ori (2 pt punctul de sus, 0 pt punctul de jos) si ca, implicit, nu vor afecta corectitudinea algoritmului.

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). Acest algoritm poate fi aplicat in rezolvarea problemei 'poligon':problema/poligon din arhiva de probleme.

*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