Având în vedere că
Mihai are un examen important mâine (admiterea), mi-am luat libertatea de a sublinia fundamentul matematic asupra căreia se poate construi o soluție corectă la această problemă în ideea că putem învăța ceva împreună. Explicația ce va urma nu este considerată unică în abordare ci doar una corectă.
Pornim de la
ipoteză : fiecare triunghi este reprezentat de coordonatele a 3 puncte și fie acele puncte A(x0,y0), B(x1,y1), C(x2,y2). În problemă mai apare un al 4-lea punct : originea. Fie originea notată, clasic, O(0,0).
Concluzie : găsirea dreptei a cărei distanță de la origine la ea este minimă.
Abordarea pe care v-o propun presupune, simplu, calculul distanței de la O la dreptele suport ale laturilor triunghiului : AB, BC, AC și alegerea, dintre aceste distanțe, a dreptei a cărei distanță este cea mai mică.
În consecință, ceea ce trebuie să aflăm noi este
distanța de la o dreaptă la un punct ( O(0,0) ).
Prin definiție, distanța de la un punct
)
la o dreaptă dată prin ecuația
este
=\frac{|ax_p+by_p+c|}{\sqrt{a^2+b^2}})
. Aplicând informațiile problemeni noastre și anume aceea că P este chiar originiea deci are coordonatele 0 și 0 => o ușurare a formulei mai sus menționate :
=\frac{|a*0+b*0+c|}{\sqrt{a^2+b^2}}=\frac{|c|}{\sqrt{a^2+b^2}})
.
Problema următoare care se pune este : cum construim acea dreaptă d având 2 puncte date A(x0,y0) și B(x1,y1) de pildă.
Pentru asta apelăm la o altă formulă cunoscută din geometrie :
Ecuaţia dreptei determinate de două puncte distincte.
Există 3 cazuri după care se construiește această ecuație :
- Dacă
atunci dreapta este orizontală şi va avea ecuaţia 
de unde identificăm coeficienții generici de mai sus : 
- Dacă
atunci dreapta este verticală şi va avea ecuaţia 
rezultând coeficienții 
. - Dacă
și 
atunci ecuația dreptei reiese din calculul expresiei (y_1-y_0)=(y-y_0)(x_1-x_0))
x+(x_0-x_1)y-x_0_y_1+\not{x_0y_0}-\not{x_0y_0}+x_1y_0=0 \tex)
Super, aproape că am terminat! Tot ce mai trebuie să facem acum este să contopim cele 2 formule rezultând 3 cazuri de a calcula distanța de la origine (O(0,0)) la dreapta noastră luată arbitrar AB cu A(x0,y0) și B(x1,y1) :
- Pentru avem
=\frac{|-y_0|}{\sqrt{0^2+1^2}}=y_0)
ceea ce este normal dacă ne gândim că dreapta este paralelă cu Ox - Pentru avem
=\frac{|-x_0|}{\sqrt{1^2+0^2}}=x_0)
ceea ce este normal dacă ne gândim că dreapta este paralelă cu Oy - Pentru și avem, mai complicat, dar de așteptat :
=\frac{|x_1y_0-x_0y_1|}{\sqrt{(y_1-y_0)^2+(x_0-x_1)^2}})
Aplicând acest raționament și pentru celelalte drepte (BC și AC) și verificând care dintre cele 3 distanțe este minimă duce, inevitabil, la rezolvarea problemei.
Problema nu a fost nici ușoară, dar nici grea. După cum se poate observa: fără cunoștințe de matematică, nu aveai cum s-o abordezi darmite să o rezolvi corect (eventual cu un random
).
Morala : stay in school and keep away from drugs
.
În altă ordine de idei : Sincere felicitări pentru toți participanții acestui concurs! În opinia mea, fericirea ar trebui să fie 80% din participare și 20% din câștig. Dacă câștigul nu este, cei 20% nu se risipesc ci se însumează la motivare. E clar că vrem mereu 100% sau mai mult dacă se poate, dar simplul fapt că v-ați lucrat tărtăcuța mereu vă cizelează spre a deveni cu toții, cândva, mai buni programatori.
Haideți să trecem printr-o analiză de bun simț sursele voastre și să remarcăm câte ceva :
sharky92:
- Un sfat referitor la variabilele globale : încearcă să nu mai depinzi așa mult de ele. Gândește-te așa : o funcție matematică primește parametrii și returnează valori, ori dacă valorile sunt într-un mediu global poluat, mai sunt acelea funcții? Sintactic da (doarde sunt compilabile), dar logic nu. Încearcă să te înveți cu parametrii. La proiecte mai mari, vei înțelege probabil mai bine de ce.
- Încearcă să-ți scindezi algoritmul de rezolvare pe funcții care au un singur scop și doar unul. Asta este valabil pentru orice funcție. Mă refer aici la build(). Când am văzut-o pentru prima dată, mă așteptam să-mi construiască și să-mi returneze ceva, dar nicidecum să îmi și scrie rezultatul în fișiere. Un nume mai sugestiv ar fi fost de un mai mare folos.
- Nu aș vrea să fac referire excesivă la cod, dar sper că asta este o greșeală de neatenție și/sau oboseală:
- pozitie poz[2];
- // ...
- for(i=0; i<=2; i++)
- f>>poz[i].p>>aux>>poz[i].x>>aux>>poz[i].y>>aux;
Vectorii nativi încep în C/C++ de la 0 (așa cum ai început și tu), dar sunt alocați până la n-1 cu n lungimea lor. Dacă n = 2 atunci ultimul element din vector la care avem acces va fi poz[1] și nu poz[2]. - Un ultim pont : când tu scrii așa : atunci tu forțezi ca pentru fiecare iterație a for-ului, înainte de compararea j<=nr-1, să se efectueze acea scădere nr-1 ceea ce consumă timp. Gândește-te dacă mai apare această problemă atunci când scriu, lafel de corect, :
- Am observat că ai abordat aceeași logică de a rezolva problema ca cea discutată mai sus. Frumos!, dar ai pierdut din cele 3 cazuri.
payne :- Se observă experiența : cod frumos formatat, categorizat fluent și ușor de urmărit. Nu prea am înțeles ce face funcția sti (se citește ști ?), dar cred că sunt eu greu de cap . Ca și hint : încearcă să folosești pasarea prin referință, mai ales în cazul în care știi că nu ți se va modifica valoarea în cadrul funcției (const-like). În felul acesta elimini duplicare de obiecte. const string no, de pildă, devine const string &no
- Felicitări pentru acel 100%
cata45:
- Utile comentarii! Practică apreciată.
- Încearcă să dai nume mai sugestive variabilelor. Nu de alta, dar vor ajunge zile în care cele 26 de litere ale alfabetului nu vor mai părea suficiente . Noroc de Unicode.
- Ceea ce te-a costat la viteză au fost procesările acelea pe șiruri. Trage tu concluziile de aici .
eni4ever:
- Atenție la enunț!
No comment! - Dacă se doresc explicații punctuale la implementare în Qt, cereți-mi-le și le voi da cu cel mai mare drag.
Cred că este suficient, deocamdată.
Aștept nerăbdător proba următoare,
Payne, ai
tastatura,
Spor, colocatari!
P.S: doritorii de a vedea sursele tester-ului le pot descărca
de aici.
by eni4ever » 11 Jul 2011, 20:19 
C11_Surse.zip
Welcome to BitCell. Click here to register !