infoarena

Am 2 puncte A(x,y) si B(x',y') si o multime de puncte de coordonate intregi. Cum as putea sa determin cu care punct din multime cele 2  formeaza un unghi maxim ? Adica cum aleg un punct C a.i. unghiul BCA sa fie maxim ?

Le parcurgi, si pentru fiecare punct P(xp,yp) faci pantele pentru dreptele AP si BA, m1 respectiv m2, apoi faci m= (m1 + m2)/(1-m1*m2). apoi pt unghi faci atan(m). Si iei maximul :D,

Sper ca te ajuta,

PS Sa-mi spui daca nu intelegi ceva

Multumesc. Dar cred ca ai vrut sa zici AP si BP :-?


EDIT : scrisesem eu aiurea ,trebuia BCA  :roll:.  Mersi inca o data  

Cel mai simplu merge cu teorema cosinusului.
Cum stii coordonatele afli lungimile laturilor cu Th Pitagora si cosinusul unghiului cu Th cosinusului. In cazul in care vrei sa afli cel mai mare unghi sub 180^o acesta va avea cosinusul minim, iar daca vrei pentru unghiurile mai mare de 180^o acesta are cosinusul maxim.(pe [0,pi] cosinusul este strict descrescator).


O metoda mai grea ar fi cu cross product prin care putem afla sinusul. Dar nu este de ajuns deoarece sinusul nu este monoton pe [0, PI].
Deci trebuie sa aflam si daca unghiul trece in cadranul 2 sau nu.
Fie d' perpendicular pe dreapta AC in punctul B', B apartine d', daca B' apartine (AC) atunci masura unghiului este mai mica de pi/2, iar daca nu apartine este mai mare.
Pentru a afla daca B' apartine (AC) trebuie sa-i aflam coordonatele.
Scriem ecuatia dreptei AC si aflam panta. Cum d' perp. pe AC produsul pantelor este -1 => panta lui d' este (-1/(panta lui AC)).
Acum stim ca (y-y_B)=panta(d')*(x-x_B) si o putem rescrie sub forma ax+by+c=0.
Putem afla astfel coordonatele lui B' din cele 2 ecuatii pe care le verifica(ecuatia dreptei d' si a dreptei AC).
Pentru a afla daca B' apartine (AC) verificam daca coordonatele lui B sunt in interiorul celui mai mic dreptunghi determinat de A si C cu laturile paralele cu axele de coordonate. Daca apartine acestui dreptunghi atunci apartine si segmentului (AC).(segmentul AC este intersectia punctelor din interiorul dreptunghiului cu axa AC pe care B' se afla din ipoteza).


Sper ca am scris bine. Daca gasiti greseli va rog sa ma corectati.

Totusi metoda asta cu cross product mi se pare mai dificila. E mult mai usor cu pantele sau teorema cosinusului.

http://cplusplus.com/reference/clibrary/cmath/atan2/

Da dar cross product e destul de folosit in probleme. Adica cu el poti afla ariile poligoanelor, poti sa afli daca 2 segmente se intersecteaza, poti sa afli infasuratoarea convexa si multe altele(vezi topcoder). Sa fiu sincer, e prima data cand folosesc teorema cosinusului la o problema de informatica.

Este buna si solutia cu tangenta unghiului format de cele 2 drepte! Poti aplica ce a zis Silviu si in cazul cand unghiul este ACB. Dar nu cred ca este nevoie sa calculezi arctangenta. Adica pe (0,pi/2) e pozitiva  si crescatoare iar pe (pi/2,pi) e negativa si crescatoare si la imagini egale ai argumente egale(in afara de 0 si pi) deci nu e nici o problema sa-ti dai seama daca unghiul x are masura mai mare ca unghiul y daca le stii tangentele.

@klamathix : Perfect !

@yonatan : Mda...trebuie sa ma pun la punct cu geometria  :weightlift: