geometrie

[•Oancea.Catalin]

Am gasit o problema data la .campion in 2008 (supertri). Un supertriunghi este un triunghi care contine un numar maxim de puncte in interior. Se dau cele n puncte si trebuie sa se scrie un supertriunghi cu coordonate din multimea data. M-am gandit ca un punct M este in triunghiul ABC daca S(MAB)+S(MAC)+S(MBC)=S(ABC) prin S(XYZ) am notat suprafata triunghiului XYZ. Evident nu va intra in 2 sec pt un n=300. Stiu ca se putea determina daca un punct apartine unui triunghi daca toate intoarcerile catre acel punct avau acelasi sens... Imi puteti da si mie o implementare?

[•scipianus]

Depinde de cat de mare e n sau timpul   Estimezi ca pentru o implementare a ideii cu ariile , aplicand formula pentru arie in functie de coordonatele varfurilor (nu calculand prostii cu distante dintre 2 puncte si Heron...) , nu ar intra in timp?  

P.S. : Pentru 3 puncte A,B,C de coordonate (x1,y1),(x2,y2),(x3,y3) ,aria triunghiului ABC este :
(1/2)*abs(x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1*y3).
Dar bineinteles pentru a testa acea egalitate nu ar mai fi nevoie sa aplici si impartirea la 2 pentru ca se face la fiecare(s-ar simplifica oricum) si ai pierde timp inutil.

[•Oancea.Catalin]

multumesc.. stiam formula aia cu matrice. Dar as vrea chestia aia cu intoarceri ... am auzit multi vorbind de ea... multumesc oricum