This problem has a very beautiful geometric solution. It's listed among "Some Geometric Gems" in the _Challenge and Thrill of Pre-College Mathematics_ book (familiar to those who participate[d] in the Maths Olympiad[s] in India!)
The idea is that if you reflect D to D_2 (about AB) and to D_3 (about AC), then, clearly, DE=D_2E and DF=D_3F, so perimeter of DEF = DE + DF + EF = D_2E + EF + D_3F, which is the length of a broken line from D_2 to D_3, and is minimum when the line is straight. (MidS: I just noticed that it's explained in (is part of) L.Fejér's solution at http://www.cut-the-knot.org/triangle/Fagnano.shtml -- move R and Q to play with it.) To calculate it, observe that AD_2=AD=AD_3, and that the angle D_2AD_3 is twice the angle BAC, and the cosine rule Our code, in case it helps (it's ugly, though): [ct is cos(BAC), c2t is cos(2*BAC)=cos(D_3AD_2)] #include <iostream> using namespace std; typedef long double ld; #define GET(x) ld x; scanf("%Lf",&x); ld sqr(ld x) { return x*x; } int main() { int ncases; scanf("%d",&ncases); while(ncases--) { GET(bc); GET(ac); GET(ab); GET(ad); ld ct = (sqr(ac)+sqr(ab)-sqr(bc))/(2*ac*ab); ld c2t = 2*sqr(ct)-1; printf("%.2Lf\n",sqrtl(2*ad*ad*(1-c2t))); } return 0; } --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
