406 Triunghi2

[•DITzoneC]

Aici puteţi discuta despre problema Triunghi2.

[•Florian]

Ar putea sa-mi spuna cineva ce este gresit la functia asta de determinare a ariei?

Cod:

int arie(int x1,int y1, int x2, int y2, int x3, int y3)
	{
	int area;
	area=(x3-x1)*(y2-y1)-(x2-x1)*(y3-y1);
	return abs(area/2);
	} 

Iau doar 70 de puncte, cu WA pe celelalte...Am testele oficiale, insa e destul de dificil de debug. Eu, pt a verifica daca un punct este in interiorul unui triunghi fac asa:

*fie ABC triunghiul, iar M, punctul al carui pozitie trebuie verificata.
*calculez aria lui ABC, lui ABM, lui ACM, lui BCM, si verific daca A(ABM)+A(BCM)+A(ACM)==A(ABC). Daca are loc conditia asta, atunci inseamna ca se afla in interior. Banuiesc k greseala este la functia de determinare a ariei...

[•pauldb]

E buna formula.

[•DITzoneC]

Ai grija ca tu acolo trunchezi aria( din x.5 tu obtii x). Poti pur si simplu sa nu mai imparti la 2 si sa verifici asa sumele alea.

[•Florian]

Incercasem si fara impartire si tot nu`mi iese. Cat va da pentru:

Cod:

Coordonatele ABC: 98 -87 -133 45 116 193 

Coordonatele M: 31 80 

Ma intereseaza care este aria triunghiului, si a celor trei triunghiuri formate de laturile ABC cu punctul M.


LE: Am renuntat la "abs" si imi da la o arie "-1". Am pus cu "abs" si imi da 0. De ce?

LE2: Am facut niste modificari, obtinand un program care nu-mi dadea bine deloc pe testele mele...Am trimis si....surpriza: 100 de puncte   E o porcarie Borland-ul..ma las de el.

LE3: Gata! Mi-am pus rhide....Alta viatza!...

[•Robytzza]

datzimi si mie ceva idei ,la al doilea punct (sa verific daca e vre un taran care ii cuprinde pe ceilaltzi ) ca nu prea imi da

[•Florian]

Pai in primul rand, daca exista un asemenea tzaran, asta inseamna ca e posesorul parcelei cu aria cea mai mare! Avand coordonatele triunghiului de arie maxima, este destul de usor sa verifici pt fiecare punct al fiecarui triunghi daca este in interiorul triunghiului de arie maxima! Deci, sa presupunem ca triunghiul de arie maxima este ABC. Pentru toate celelalte triunghiuri de forma DEF, verifici dak D, E, respectiv F sunt in interiorul lui ABC. Este de ajuns k acest lucru sa fie fals o singura data si te poti opri. Succes! 

[•Robytzza]

oky o sa incerc asa ms mult 

[•vanila_CPP]

eu iau 100 pe testele de la ONI si totusi sursa mea continua sa ia 20 in arhiva
e vreo regula de afisare?(ceva cu spatii intre numere sau chestii de genu)??

[•toni2007]

poate e din cauza ca afli gresit aria... si eu la inceput luam 65-70 de puncte din cauza ca faceam functia de aflare a ariei double...
dupaia am facut-o int si am impartit la 2 la sfarsit (la afisare)si am luat 100... cred ca e un bug al c-ului (e ciudat dar nu imi aproxima corect x/2)... nuj incearca asa...

[•vanila_CPP]

eu calculam aria cu heron. nu stiu de ce dar busea. acum am calculat cu determinanti si merge

[•astronomy]

Apar erori de precizie daca faci cu formula lui heron.

[•Mishu91]

Cod:

int arie(int x1,int y1, int x2, int y2, int x3, int y3)
	{
	int area;
	area=(x3-x1)*(y2-y1)-(x2-x1)*(y3-y1);
	return abs(area/2);
	} 

Exista vreo demonstratie a formulei, pentru ca nu ma prea prind 

[•toni2007]

da vezi ca tu nu faci bine  faci functia int si cand returnezi area/2 iti face parte intreaga si pentru arie 13.5 de exemplu tie iti da area=27 si tu returnezi 26... daca vrei pui functia double sau returnezi fara impartirea la 2.

si eu din cate stiu aria se facea cu o chestie care am uitat cum se numeste

ceva gen o chestie pentru  |a b c |      | x1 y1 1 |
                                     |d e f  | =   | x2 y2 1 |
                                     |g h i  |      | x3 y3 1 |

care e  aei + dhc + bfg - ceg - dbi - hfa deci x1y2 + x2y3 + x3y1 - x3y2 - x2y1 - x1y3 de unde formula (dai factor comun)

citeste mai multe aici http://www.softsurfer.com/Archive/algorithm_0101/algorithm_0101.htm

[•Mishu91]

Mersi fain... kiar tare formula  adik fata de formula lu Heron la care calculezi de mori si tot nu da bine asta kiar super misto

[•devilkind]

si eu din cate stie aria se facea cu o chestie care am uitat cum se numeste

chestia aia se numeste determinant

[•toni2007]

da ms uitasem

[•ciprianf]

Editat de moderator: Nu postati rezolvari complete! Mai ales cand nu vi le cere nimeni!

[•gabitzish1]

Puteai sa il lasi pe fiecare sa isi frece putin mintea si sa se prinda singur de rezolvare. 

[•ciprianf]

Nu am vrut decat sa ajut... ....oricum si metoda cu aria e destul de clar explicata ...daca e prea detaliat, rog un admin sa-mi stearga postul

[•pauldb]

Puteai sa il lasi pe fiecare sa isi frece putin mintea si sa se prinda singur de rezolvare. 

S-a rezolvat.

[•tvlad]

Intra lejer si brut la punctul 2

[•bacerandrei]

Dezgrop si eu acest subiect...pentru ca m-am apucat sa ma perfectionez la capitolul geometrie la care nu stau prea bine

Deci, la punctul 1 verific pentru fiecare triunghi daca punctul ce reprezinta fantana se afla in interiorul triunghiului, folosind determinanti.
La punctul 2 aflu triunghiul de arie maxima, iar pentru fiecare triunghi verific apoi daca fiecare varf al lui se afla in interiorul triunghiului de arie maxima.

Imi poate spune cineva, va rog, unde gresesc?

[•DraStiK]

Dezgrop si eu acest subiect...pentru ca m-am apucat sa ma perfectionez la capitolul geometrie la care nu stau prea bine

Deci, la punctul 1 verific pentru fiecare triunghi daca punctul ce reprezinta fantana se afla in interiorul triunghiului, folosind determinanti.
La punctul 2 aflu triunghiul de arie maxima, iar pentru fiecare triunghi verific apoi daca fiecare varf al lui se afla in interiorul triunghiului de arie maxima.

Imi poate spune cineva, va rog, unde gresesc?

ideea de rezolvare este corecta, nefiind nimic gresit

cel mai probabil gresesti la implementare
vezi sa fii atent si la faptul ca aria se imparte la 2 (la calcului cu determinati) si in rest nu prea mai sunt cazuri speciale

daca nu reusesti dami un pm

[•bacerandrei]

Impart aria la 2, iar ca sa vad daca un punct e interior unui triunghi fac cei trei determinanti si verific daca au acelasi semn. Inca nu pot sa imi dau seama unde e gresita implementarea. Probabil nu sunt suficient de atent.