*{+Solutia 1+}*

Se ia un varf al poligonului, si se traseaza cele $n-3$ diagonale care pornesc din el. Astfel poligonul nostru se imparte in mai multe triunghiuri. Vom adauga intr-un vector aceste drepte plus cele $2$ laturi care au originea in varful ales de noi si le sortam dupa panta. Cand primim un query vom cauta binar dupa panta si vom afla intre ce diagonale se incadreaza acesta si verificam daca punctul nostru se afla sau nu in triunghiul respectiv.

Se ia un varf al poligonului, si se traseaza cele $n-3$ diagonale care pornesc din el. Astfel poligonul nostru se imparte in mai multe triunghiuri. Vom adauga intr-un vector aceste drepte plus cele $2$ laturi care au originea in varful ales de noi si le sortam dupa panta. Cand primim un query vom cauta binar dupa panta si vom afla intre ce diagonale se incadreaza acesta si verificam daca punctul nostru se afla sau nu in triunghiul respectiv.
Sa luam un exemplu:
!notiuni-de-geometrie-si-aplicatii?polig1!
In imaginea de mai sus punctele $P{~1~}$,..{$P{~6~}$} reprezinta varfurile poligonului iar punctele $P{~7~}$, $P{~8~}$, $P{~9~}$ reprezinta interogarile. Cu rosu sunt trasate diagonalele care delimiteaza sectoarele, si le vom tine ca drepte, sortate dupa panta, impreuna cu dreptele suport pentru cele 2 laturi care au un capat in punctul $P{~1~}$. Astfel cand primim o interogare vom putea cauta binar si sa aflam in ce sector se afla acesta. Pentru punctul $P{~8~}$ spre exemplu ne vom da seama ca se afla in sectorul determinat de diagonalele care corespund punctelor $P{~4~}$ si $P{~5~}$. Astfel vom verifica daca punctul $P{~8~}$ se afla in interiorul triunghiului determinat de punctele $P{~1~}$, $P{~4~}$, $P{~5~}$. Vom proceda asemanator si pentru celelalte interogari cu mentiunea ca trebuie sa avem grija la cazurile in care punctul nu se afla in nici unul din sectoare, insa asta se poate face usor cu o verificare inainte de a porni cautarea binara.

h1. TODO