h2. Drepte

h3. Ecuatiile dreptei

h3. {+Ecuatiile dreptei+}

Dreptele sunt locuri geometrice ce indeplinesc _ecuatia dreptei_. Cu alte cuvinte, ecuatia unei drepte reprezinta o relatie care este respectata de toate punctele aflate pe dreapta. Forma generala a ecuatiei unei drepte in sistemul $xOy$ este

*Feedback (Stefan):* Pare destul de trivial/pueril/nefondat raspunsul la intrebarea "de ce toate ecuatiile sunt (in general) egale cu 0?". Se poate gasi o motivatie mai buna sau se poate renunta la ea.
*Edit (Cotizo):* Fixed, de asemenea... fac topic pentru articol si bag acolo sugestiile + TODO existent ?

h3. Punctul de intersectie a 2 drepte

h3. {+Punctul de intersectie a 2 drepte+}

Dupa cum am vazut, o dreapta reprezinta un loc geometric. Sa zicem ca avem 2 drepte $d{~1~}$ si $d{~2~}$ si dorim sa aflam punctul $A(x, y)$ cu propietatea ca acesta apartine atat dreptei $d{~1~}$, cat si dreptei $d{~2~}$. Scriem ecuatiile celor 2 drepte:

<tex>y = \frac{\mbox{-c_1 - a_1 * x}}{\mbox{b_1}}</tex>
*TODO:* Fractiile arata prea mici cu LaTeX. Asta trebuie fixat cumva. FIXED (desi nu merge peste tot)

h3. Panta unei drepte

h3. {+Panta unei drepte+}

Panta unei drepte se poate defini ca fiind tangenta unghiului facut de dreapta cu orizontala, mai exact cu orice dreapta paralela cu axa $OX$. Ea se calculeaza astfel:

h2. Distante

h3. Distanta dintre 2 puncte

h3. {+Distanta dintre 2 puncte+}

Consideram $2$ puncte $A(x{~1~},y{~1~})$ si $B(x{~2~},y{~2~})$, si vrem sa aflam distanta dintre ele. Pentru a face acest lucru construim un al treilea punct $C(x{~2~},y{~1~})$ si observam ca triunghiul $ACB$ este dreptunghic iar distanta dintre punctele $AB$ este intocmai ipotenuza acestui triunghi. Folosind "teorema lui Pitagora":http://mathworld.wolfram.com/PythagoreanTheorem.html ajunge la urmatoarea formula:
<tex>d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}</tex>

h3. Distanta dintre un punct si o dreapta

h3. {+Distanta dintre un punct si o dreapta+}

Pentru a calcula distanta care ne trebuie noua vom calcula panta dreptei $d{~1~}$ notata cu $m{~1~}$. Acum vrem sa construim o dreapta $d{~2~}$ perpendiculara pe dreapta $d{~1~}$ care trece prin punctul $A$. Stim ca $m{~1~}*m{~2~}=-1$ si de aici aflam usor $m{~2~}$ (panta dreptei $d{~2~}$). In acest moment avem panta dreptei $d{~2~}$ si un punct care ii apartine. Avand aceste 2 informatii putem sa calculam usor ecuatia ei si punctul de intersectie cu dreapta $d{~1~}$ ({_Vezi capitolul Drepte_}). Distanta dintre dreapta si punct va fi egala cu distanta dintre punct si punctul de intersectie al celor $2$ drepte.
De asemenea exista si o formula pt a determina distanta de la un punct la o dreapta: considerand punctul $A(x{~0~},y{~0~})$ si dreapta $d:ax+by+c=0$, vom avea :
<tex> d(A,d) = \frac{|\mbox{a\cdot x_0+b\cdot y_0+c}|}{\mbox{\sqrt{a^2+b^2}}}</tex>

h3. Distanta dintre un punct si un segment

h3. {+Distanta dintre un punct si un segment+}

Sa presupunem un punct $A(x{~1~},y{~1~})$ si un segment determinat de punctele $B(x{~2~},y{~2~})$ si $C(x{~3~},y{~3~})$ si vrem sa aflam distanta dintre punct si segment.

h2. Arii

h3. Aria unui triunghi

h3. {+Aria unui triunghi+}

Aria unui triunghi determinat de punctele $A(x{~1~},y{~1~})$, $B(x{~2~},y{~2~})$ si $C(x{~3~},y{~3~})$ este egala cu :

Unde $abs(x)$ reprezinta valoarea absoluta a lui $x$. Determinantul de mai sus poate fi folosit si pentru a vedea daca cele $3$ puncte sunt in sens invers sau direct trigonometric, el fiind negativ in cazul in care punctele sunt in sens invers trigonometric.

h3. Aria unui poligon

h3. {+Aria unui poligon+}

Aria unui poligon convex cu $n$ laturi o putem calcula foarte usor folosind formula pentru aria unui triunghi astfel.

h2. Probleme rezolvate

h3. Infasuratoarea convexa

h3. {+Infasuratoarea convexa+}

Enuntul problemei: Se da un set de puncte in plan, sa se determine un poligon convex de arie minima care contine toate punctele in interiorul sau.
Rezolvare: O posibila solutie este sa fixam punctul cu abscisa minima ,iar in caz de egalitate luam punctul cu ordonata minima, si sa translatam toate punctele pana cand acesta ajunge in punctul de coordonate $(0,0)$. Acum vom sorta punctele dupa formula <tex> \frac{y}{x} </tex> unde $x$ si $y$ sunt coordonatele punctului, iar in caz de egalitate dupa distanta fata de punctul $(0,0)$. In cazul nefericit in care $x=0$ vom considera ca <tex> \frac{y}{x} = INF </tex>. Apoi vom parcurge punctele in ordine si le vom introduce intr-o stiva. Inainte sa introducem un punct in stiva trebuie insa sa ne uitam daca nu cumva punctele $st[vf-1] , st[vf]$ si $P$ sunt in ordine invers trigonometrica ( $st$ - stiva, $vf$ - varful stivei, $P$ - punctul curent). Aici ne vom folosi de o alta proprietate a determinantului cu ajutorul caruia determinam aria unui triunghi. Mai exact vom calcula

pentru $st[vf-1] = (x{~1~}.y{~1~}) , st[vf]= (x{~2~},y{~3~}), P(x{~3~},y{~3~})$. Daca $D$ este negativ atunci inseamna ca unghiul cu originea in $st[vf]$ face o intoarcere la dreapta si trebuie scos din stiva. Repetam procedeul pana cand ramanem cu un singur punct in stiva sau pana cand intalnim un $D >= 0$ dupa care adaugam punctul in stiva. Dupa ce am terminat e posibil ca poligonul nostru inca sa fie convex deoarece nu am verificat unghiul care are originea in $st[vf]$, asa ca il vom calcula pe $D$ pentru punctele $st[vf-1],st[vf],st[ 1 ]$ si vom scoate punctul din varf atata timp cat $D$ va fi negativ. Punctele ramase reprezinta infasuratoarea convexa a setului de puncte primite la intrare.
*devilkind*: E posibil sa nu fi inteles eu bine, dar la faza cand y/x e 0 cred ca trebui sa pui INF sau -INF in functie de semnul lui y. nush daca merge doar cu INF. - FIXED

h3. Punct in interiorul unui triunghi

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!

det( ((xA,yA,1),(xB,yB,1),(xP,yP,1)) ), det( ((xB,yB,1),(xC,yC,1),(xP,yP,1)) ), det( ((xC,yC,1),(xA,yA,1),(xP,yP,1)) )

trebuie sa aiba acelasi semn. In caz contrar, $P$ este in exteriorul triunghiului. In imaginea precedenta, se observa ca in cazul punctului $P'$, vectorii **BC**, **CP** fac o intoarcere la dreapta, deci determinantul corespunzator nu va avea acelasi semn cu ceilalti doi.

trebuie sa aiba acelasi semn. In caz contrar, $P$ este in exteriorul triunghiului. In imaginea precedenta, se observa ca in cazul punctului $P'$, vectorii **BC**, **CP** fac o intoarcere la dreapta, deci determinantul corespunzator nu va avea acelasi semn cu ceilalti doi.
Aceasta idee poate fi generalizata pentru a fi determina daca un punct se afla in interiorul unui poligon convex in $O(N)$. Mai exact se calculeaza det( (x{~i~},y{~i~},1), (x{~i+1~}, y{~i+1~}, 1) (x{~p~},y{~p~},1) ) pentru $i$ luand valori de la $1$ la $N$ (cand $i$=={$N$} vom considera $i+1=1$) . Punctul P(x{~p~},y{~p~}) se afla in interiorul poligonului daca si numai daca toti determinanti au acelasi semn. ( "+" daca parcurgem poligonul in sens direct trigonometric, "-" altfel)

h3. Punct in interiorul unui poligon oarecare

h3. {+Punct in interiorul unui poligon oarecare+}

Se da un poligon oarecare cu $N$ varfuri si un punct $P$ prin coordonatele carteziene. Se cere sa se determine daca punctul $P$ este in interiorul sau in exteriorul poligonului.

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). In acest caz, nu vom numara nici una dintre muchii ca fiind intersectata de semidreapta. Vom considera imaginea urmatoare:

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!

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 ... si avem o problema

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 ... si avem o problema. Pentru a rezolva 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.
*devilkind* - am dat eu o solutie care merge destul de bine ptr cazul in care semidreapta orizontala intersecteaza varfuri insa e cam jegoasa asa (tre sa calculezi intersectii de drepte si e cam aiurea). Era un smen in care considerai ca numai un capat al laturii face parte din ea, dar nu mai stiu cum era.
h3. {+Punct in poligon convex+}
 
Enunt: Se da un poligon convex cu $N$ laturi si apoi $M$ interogari caracterizate prin coordonatele unui punct $P$, iar dumneavoastra trebuie sa raspundeti rapid daca punctul respectiv se afla sau nu in interiorul poligonului.
 
*{+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.
 
 
 
h1. TODO

*Feedback (Stefan):* Articolul trebuie imbracat intr-o forma mai prezentabila. Nu trebuie sa ramana doar o lista de formule si schelete de probleme. De asemenea, trebuie compactat si eliminate spatiile mari care il fac greu de citit.
*TODO:* Adaugati si centru de greutate a unui poligon si eventual explicati de ce merge formula de mai sus pt aria unui poligon concav.