|
Titlul: geometrie Scris de: Oancea Catalin din Iunie 06, 2011, 18:04:50 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? :) :peacefingers:
Titlul: Răspuns: geometrie Scris de: FMI Ciprian Olariu din Iunie 06, 2011, 18:22:15 Depinde de cat de mare e n sau timpul :-k 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? #-o
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. Titlul: Răspuns: geometrie Scris de: Oancea Catalin din Iunie 06, 2011, 18:30:33 multumesc.. stiam formula aia cu matrice. Dar as vrea chestia aia cu intoarceri ... am auzit multi vorbind de ea... multumesc oricum
|