infoarena

http://acm.sgu.ru/problem.php?contest=0&problem=162

Voi cum ati facut cu erorile de precizie?

Nu ma descurc deloc din punctul asta de vedere pe SGU. Nu e singura problema de geometrie unde iau WA :(.

Eu fac asa:
1. Calculez:
Aria unui triunghi cu Heron.
Inaltimea unui triunghi = 2*Aria/baza.
2. Aflu S = Aria bazei, apoi aflu HB = inaltimea in triunghiul pe care il consider baza piramidei pe una din laturi (sa o notam cu A), apoi HL = inaltimea din varf pe fata laterala care contine pe A, H = inaltimea in triunghiul determinat de HB, HL si latura care i se opune lui A.
3. Afisez S*H/3.

Interesant e ca daca variez varful sau latura A, primesc rezultate diferite de la a 3a zecimala (chiar si pe long double).

In primul rand nu mai calcula ariile triunghiurilor cu Heron.. e cea mai proasta metoda din punct de vedere  al preciziei.

Cea mai simpla metoda e cu un determinant, poti sa vezi aici: http://en.wikipedia.org/wiki/Tetrahedron

Am facut eu treaba cu determinant astfel:

Dupa cum am invatat eu la mate, un determinant de ordin N poate fi scris ca o suma de N! termeni, acestia fiind produse de N elemente si pot fi aflate generand toate permutarile de ordin N. Semnul fiecarui termen il aflu in functie de paritatea numarului de inversiuni. Buuun... si toata frumusetea asta de determinant o sa fie intreg tot timpul. Sunt absolut sigur ca pana aici nu apar erori de precizie, ca doar sunt intregi. Tin pe long double treaba ca sa fiu sigur.

Apoi afisez sqrt(determinant/2)/12 si iau WA pe testu 16.

Mi se pare ca pentru long double trebuie sa folosesti sqrtl ... altceva nu stiu ce ar putea fi  :-s

Daca nu merge si nu merge.. poti oricand sa cauti binar rezultatul pe intregi (sau numere mari) cu precizia care trebuie  :P

Merge cu determinant pe long long si sqrt fara cine stie ce batai de cap... doar ca am impresia ca e vorba de alt determinant. Faci cu formula de pe wikipedia?

Mersi maestre, in sfarsit AC.

Am schimbat determinantul ala din long double in long long si a mers. O fi de la minunatul Visual de pe SGU? Pe calculatorul meu am dat teste si primeam acelasi rezultat.

Simt o nota de ironie.  :P


Na, erori de precizie tampite, ce sa le faci... dar era inutil sa faci calculele pe numere reale pentru ca la fiecare pas poate exista o mica abatere si din moment ce se face un numar de calcule sunt ceva sanse sa se acumuleze la a 4-a zecimala, presupun.

Ti se pare, iti spuneam asa si cateodata cand ne intalneam in Jack :P.

Mircea zice ca se presupune ca long double nu pierde precizie cand toate valorile sunt intregi, eu nu stiam faza asta. Daca asa stau lucrurile inseamna ca e dubios compilatorul din VC...  #-o

Parca zicea misof ca precizia la long double depinde de compilator si mai zicea pe acolo ca pt optimizare se tot schimba double in long double si dupaia rezultatu se converteste inapoi la double ... deci nu poti sa fi sigur cum se vor evalua expresiile. Mai bine inti unde se poate.