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

(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

h2. Drepte

h2(#introducere). 0. Introducere

h3. Ecuatiile dreptei

**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.

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

Î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.

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

In cazul in care dreapta nu este in plan, se va adauga un coeficient nou la ecuatie pentru fiecare dimensiune. De exemplu, pentru o dreapta in spatiu, ecuatia ei va fi
 
<tex>(d): a*x + b*y + c*z + d = 0</tex>
 
*Feedback (Stefan):* Ai cam incurcat treburile. Asta e ecuatia planului. :)
 
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 poate ridica intrebarea "de ce toate ecuatiile sunt (in general) egale cu 0?". Raspunsul este unul extrem de simplu: _dreptele sunt locuri geometrice_ (multimi de puncte cu aceeasi proprietate) _pentru care ecuatia respectiva este egala cu $0$_. De asemenea, 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.
 
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{c_2 * b_1 - c_1 * b_2}{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{-c_1 - a_1 * x}{b_1}</tex>
 
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:
 
!/notiuni-de-geometrie-si-aplicatii?action=download&file=panta.gif!
 
sau
 
!/notiuni-de-geometrie-si-aplicatii?action=download&file=ecuatie005.gif!
 
In a doua ecuatie $a$ si $b$ reprezinta coeficienti ecuatiei dreptei respective
 
!/notiuni-de-geometrie-si-aplicatii?action=download&file=ecuatie001.gif!
 
 
Propietati:
 {*} Doua drepte care au pantele egale sunt ori paralele ori confundate.
 {*} Doua drepte care au produsul pantelor egal cu $-1$ sunt perpendiculare.
 
h2. 2.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:
 
!/notiuni-de-geometrie-si-aplicatii?action=download&file=ecuatie008.gif!
 
 
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,y)$ si dreapta $d: ax+by+c=0$, vom avea :
 
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. 3.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=abs( \frac{1}{2}*\left| \begin{array}{ccc}
\ x{~1~}& y{~1~}& 1\\
x{~2~}& y{~2~}& 1\\
x{~3~}& y{~3~}& 1\end{array} \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.
 
 
 
(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