h1. 'Dreapta':problema/dreapta

Pentru inceput trebuie observat ca orice punct din interiorul unui poligon are urmatoarea proprietate:

Pentru inceput trebuie observat orice punct din interiorul unui poligon are urmatoarea proprietate:

* Exista cel putin o dreapta care trece prin acel punct astfel incat daca se taie dreapta in doua semidrepte (cu capatul semidreptelor in punctul respectiv), ambele semidrepte intersecteaza poligonul intr-un numar impar de laturi.

Folosind aceasta observatie ne putem gandi la o abordare de genul urmator:

Folosind aceasta observatie ne putem gandi la abordare de genul urmator:

* Calculam punctele de intersectie ale dreptei pe care se afla toate punctele din query-uri cu laturile poligonului
* Sortam punctele de intersectie dupa $x$ si daca sunt egale dupa $y$

public

protected