(Categoria _Geometrie_, Autori _Savin Tiberiu_ si _Sima Mihai Cotizo_)
(toc){width: 27em}*{text-align:center} *Conţinut:*

* 0. Introducere

* '**0. Introducere**':notiuni-de-geometrie-si-aplicatii#introducere

* '1. Arii':notiuni-de-geometrie-si-aplicatii/arii

** - triunghi
** - patrulater
** - poligon

** '- 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
** - ecuatii
** - distanta punct-linie
** - distanta punct-segment(semidreapta)
* '3. Punct in poligon':notiuni-de-geometrie-si-aplicatii/punct-in-poligon
** - crossing-number
** - winding-number (?)
** - smenuri
* '4. Intersectii de drepte si segmente':notiuni-de-geometrie-si-aplicati/intersectii-drepte-si-segmente
* 5. Distante
** - intre linii
** - intre segmente si semidrepte
** - cel mai mica distanta intre doua mobile

** '- 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. Infasuratoare convexa':notiuni-de-geometrie-si-aplicatii/infasuratoare-convexa
* 8. Puncte extreme si distanta poligon-linie

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

h2. Distante

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

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>
 
 
 
h2. Arii
 
 
h2. Probleme rezolvate
 
 
 
 
h3. {+Cele mai departate doua puncte+}
 
Enunt: Se da o multime de $N$ puncte in plan. Sa se determine perechea de puncte pentru care distanta dintre cele doua este maxima.
 
O prima solutie ar fi calcularea distantei intre fiecare pereche de $2$ puncte si pastrarea ca solutie a perechei cu distanta maxima. Desigur, aceasta solutie are complexitate {$O(N^2^)$} si nu este eficienta.
 
O rezolvare mai eficienta porneste de la observatia ca perechea cautata se afla in mod evident pe infasuratoarea convexa a punctelor. Vom incepe prin a fixa un punct oarecare pe infasuratoare si vom parcurge restul punctelor de pe infasuratoare in oricare sens (trigonometric sau orar). Distanta intre punctul fixat si punctul la care am ajuns in parcugere va creste pana la un moment dat si apoi va incepe sa scada. Retinem punctul aflat la distanta maxima fata de cel fixat. Vom avea acum perechea de puncte $X$ (punctul fixat initial), $Y$ (cel mai departat punct de acesta) care este o posibila solutie.
 
Apoi vom pleca de la $X$ si vom continua sa parcurgem restul punctelor de pe infasuratoare in sensul ales initial. Pentru fiecare punct din aceasta parcurgere, vom incerca sa gasim punctul de pe infasuratoare pentru care se obtine o distanta maxima. Daca am reface algoritmul folosit pentru $X$ am obtine o complexitate de {$O(N^2^)$} ceea ce este ineficient. Ca sa reducem complexitatea, notam punctul la care am ajuns in parcurgere cu $A$, si observam ca pentru oricare punct dintre $A$ si $Y$ in sensul ales, distanta intre acesta si $A$ va fi mai mica decat distanta dintre $X$ si $Y$, asadar nu poate fi o solutie. Astfel, pentru fiecare punct $A$, parcurgem punctele incepand cu punctul $Y$ in sensul ales pana cand distanta dintre $A$ si punctul la care am ajuns va incepe sa scada. Pastram distanta maxima, inlocuim perechea $X$, $Y$ cu perechea $A$, cel mai departat punct de el, verificam daca este mai buna decat solutia obtinuta pana acum si apoi trecem la urmatorul punct $A$.
 
Complexitatea acestei solutii este de {$O(N*log N)$} pentru infasuratoare si {$O(N)$} pentru aflarea celor mai departate 2 puncte asadar {$O(N*log N)$}.
 
*Algoritmul asta e gresit sunt cazuri pe care nu merge. Sunt poligoane pe care daca mergi cu al 2-lea punct la inceput distanta creste, apoi scade apoi creste si iar scade. De aia tii tot timpu un segment pe contur si cauti cel mai departat punct de segment. E un algoritm ce il bushesti usor si ar merita explicat clar si explicat de ce nu merge cu 2 puncte.*
 
 
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.
 
sugestii de probleme de adaugat
 
punct in poligon:
  - punct in triunghi [ok]
  - punct in poligon oarecare [ok]
  - punct in poligon convex 2 solutii cautare binara dupa unghi sau dupa y [ok]
  - punct in poligon stelat [ce e poligon stelat?] poligon ce are un punct din care vezi tot interiorul http://www.spoj.pl/problems/FSHEEP/
  - problema poligon din arhiva [ok, cred]
 
infasuratoare convexa - DONE
  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 [ok i guess]
  - dreptunghiul de arie minima ce contine un set de puncte
 
halplane intersection