(Categoria _Geometrie_, Autori _Savin Tiberiu_ si _Sima Mihai Cotizo_)

h2. Drepte

(toc){width: 27em}*{text-align:center} *Conţinut:*
* '**0. Introducere**':notiuni-de-geometrie-si-aplicatii#introducere
* '1. Arii':notiuni-de-geometrie-si-aplicatii/arii
** '- triunghi':notiuni-de-geometrie-si-aplicatii/arii#triunghi
** '- patrulater':notiuni-de-geometrie-si-aplicatii/arii#patrulater
** '- poligon':notiuni-de-geometrie-si-aplicatii/arii#poligon
* '2. Drepte':notiuni-de-geometrie-si-aplicatii/drepte
** '- elemente generale':notiuni-de-geometrie-si-aplicatii/drepte#general
** '- ecuaţii':notiuni-de-geometrie-si-aplicatii/drepte#ecuatii
** '- distanţa punct-linie':notiuni-de-geometrie-si-aplicatii/drepte#dpl
** '- distanţa punct-segment(semidreaptă)':notiuni-de-geometrie-si-aplicatii/drepte#dps
* '3. Punct în poligon':notiuni-de-geometrie-si-aplicatii/punct-in-poligon
** '- crossing-number':notiuni-de-geometrie-si-aplicatii/punct-in-poligon#cn
** '- winding-number (?)':notiuni-de-geometrie-si-aplicatii/punct-in-poligon#wn
** '- şmenuri':notiuni-de-geometrie-si-aplicatii/punct-in-poligon#smen
* '4. Intersecţii de drepte şi segmente':notiuni-de-geometrie-si-aplicati/intersectii-drepte-si-segmente
* 5. Distanţe
** - între linii
** - între segmente şi semidrepte
** - cea mai mică distanţă între două mobile
* 6. Bounding ...
** - ... box
** - ... circle
* '7. Infaşurătoare convexă':notiuni-de-geometrie-si-aplicatii/infasuratoare-convexa
* 8. Puncte extreme şi distanţa poligon-linie
* 9. Tangente
* 10. Probleme de concurs

h3. Ecuatiile dreptei

h2(#introducere). 0. Introducere

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

**Geometria** (din greaca veche - {_geo_}=pământ, {_metria_}=a măsura) este partea matematicii care se ocupă cu problemele privind dimensiunile, forma şi poziţia figurilor. Introducerea coordonatelor de către René Descartes a dus la dezvoltarea geometriei analitice, a cărei scop devine studierea geometriei prin funcţii şi ecuaţii.

<tex>(d): a*x + b*y + c = 0</tex>

În problemele de olimpiadă este necesară cunoaşterea câtorva noţiuni şi idei de bază pentru a facilita găsirea unui algoritm eficient într-un timp scurt. Prezentul articol are ca scop explicarea acestor noţiuni privitoare la geometria plană (2D) şi studierea câtorva idei aplicate în problemele de concurs.

In cazul in care dreapta nu se afla in plan, fiecare punct $A$ ( $x1$ , $x2$ , $x3$ ,... $Xn$ ) (pentru n dimensiuni) de pe ea va indeplini conditiile:
<tex>
$$\left\{\begin{array}{lr}
x_1 = x_0_1 + a_1; \\
x_2 = x_0_2 + a_2; \\
... \\
x_n = x_0_n + a_n;
\end{array}\right
$$
</tex>
 
A nu se confunda cu ecuatia planului:
 
<tex>(d): a*x + b*y + c*z + d = 0</tex>
 
*Feedback (Stefan):* Ai cam incurcat treburile. Asta e ecuatia planului. :)
*Edit (Cotizo):* Fixed :)
 
Pentru simplitate, de aici inainte ne vom referi numai la drepte in plan. De mentionat este faptul ca daca trecem pe $y$ in partea dreapta si impartim prin $-b$ (consideram un caz general, nu cel nefericit in care $b=0$), obtinem:
 
<tex>(d): y = \frac{(-a)}{b}*x + \frac{(-c)}{b}</tex>
 
<tex>(d): y = m*x + n</tex>, unde <tex>m=-\frac{a}{b}, n=-\frac{c}{b}</tex>
 
De asemenea, fiind date doua puncte $A(x{~1~}, y{~1~})$ si $B(x{~2~}, y{~2~})$, ecuatia dreptei determinate de ele se poate scrie
 
<tex>(d): \frac{x-x_1}{x_2-x_1} = \frac{y-y_1}{y_2-y_1}</tex>
 
Aceasta poate sa nu ne fie de prea mare ajutor, dar facand produsul mezilor cu extremii si desfacand parantezele vom obtine <tex>(d): (y_1-y_2)*x + (x_2-x_1)*y + (x_1*y_2-x_2*y_1) = 0</tex>, de unde putem deduce foarte usor cine sunt $a$, $b$, $c$ din scrierile precedente.
 
Se stie ca orice dreapta imparte planul in 2 semiplane: cel cu puncte pentru care, daca aplicam ecuatia, vom obtine o valoare strict pozitiva, si cel pentru care vom obtine o valoare strict negativa. De aceea, daca avem o dreapta data prin 2 puncte $A(x{~1~}, y{~1~})$ si $B(x{~2~}, y{~2~})$ de pe aceasta, atunci punctul $C(x{~3~}, y{~3~})$ va apartine dreptei $AB$ daca si numai daca
 
<tex>\left| \begin{array}{ccc}
x_1 & y_1 & 1 \\
x_2 & y_2 & 1 \\
x_3 & y_3 & 1 \end{array} \right| = 0</tex>
 
*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
 
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> a_1 * x + b_1 * y + c_1 = 0</tex>
<tex> a_2 * x + b_2 * y + c_2 = 0</tex>
 
Am ajuns astfel la un sistem de 2 ecuatii cu 2 necunoscute. Pentru a ajunge la niste formule mai directe de calculare a celor 2 coordonate vom inmulti prima relatie cu $b{~2~}$ si pe cea de-a doua cu $b{~1~}$.
 
<tex>a_1 * b_2 * x + b_1 * b_2 * y + c_1 * b_2 = 0</tex>
<tex>a_2 * b_1 * x + b_1 * b_2 * y + c_2 * b_1 = 0</tex>
 
Scadem cele doua relatii si ajungem la o singura ecuatie cu o singura necunoscuta:
 
<tex>(a_1 * b_2 - a_2 * b_1) * x + c_1 * b_2 - c_2 * b_1 = 0 \Leftrightarrow</tex>
<tex>x = \frac{\mbox{c_2 * b_1 - c_1 * b_2}}{\mbox{a_1 * b_2 - a_2 * b_1}}</tex>
 
O data ce l-am aflat pe $x$, descoperirea celeilalte coordonate e destul de triviala:
 
<tex>a_1*x + b_1 * y + c_1 = 0</tex>
<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
 
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:
 
<tex>m = \frac{y_1-y_2}{x_1-x_2}</tex> sau <tex>m = -\frac{a}{b}</tex>
 
In a doua ecuatie $a$ si $b$ reprezinta coeficientii ecuatiei dreptei respective
 
<tex>(d): a*x + b*y + c = 0</tex>
 
Proprietati:
 {*} Doua drepte care au pantele egale sunt ori paralele ori confundate.
 {*} Doua drepte care au produsul pantelor egal cu $-1$ sunt perpendiculare.
 
h2. Distante
 
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
 
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
 
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.
 
$D$=min(dist({$A$},{$B$}),dist({$A$},{$C$})) in cazul in care perpendiculara din punctul $A$ pe dreapta $BC$ *nu* cade in interiorul segmentului $BC$, altfel distanta va fi egala cu distanta dintre punctul $A$ si dreapta $BC$, lucru care l-am tratat mai sus.
 
h2. Arii
 
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 :
 
<tex>A = \frac{1}{2} * abs \left( \left| \begin{array}{ccc}
\ x_1 & y_1 & 1\\
x_2 & y_2 & 1\\
x_3 & y_3 & 1\end{array} \right| \right)
</tex>
 
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
 
Aria unui poligon convex cu $n$ laturi o putem calcula foarte usor folosind formula pentru aria unui triunghi astfel.
 
<tex>\displaystyle \sum_{i=2}^{i<n} Arie(p_{1},p_{i},p_{i+1})</tex>
 
Unde <tex>Arie(p_{x},p_{y},p_{z})</tex> reprezinta aria triunghiului determinat de punctele $p{~x~}$, $p{~y~}$, $p{~z~}$.
 
Aria unui poligon concav se calculeaza la fel doar ca atunci cand calculam <tex>Arie(p_{1},p_{i},p_{i+1}</tex> renuntam la abs, si tinem minte semnul determinantului si luam valoarea absoluta dupa ce am calculat intreaga suma.
 
h2. Probleme rezolvate
 
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 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
<tex>D=\left| \begin{array}{ccc}
\ x_1 & y_1 & 1\\
x_2 & y_2 & 1\\
x_3 & y_3 & 1\end{array} \right|
</tex>
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.
 
*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.
 
sugestii de probleme de adaugat
 
punct in poligon:
  - 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 X
  vreo 5 metode
 
gasire rapida a celui mai de sus punct din un poligon convex
 
determinare daca un poligon e convex sau concav
 
determinare a sensului de parcurgere a varfurilor unui poligon
 
intersectii de drepte cu un poligon convex
 
rotating calipers
  - perechea de puncte cele mai departate
  - dreptunghiul de arie minima ce contine un set de puncte
 
halplane intersection