[LightOJ ] 1043- Triangle Partitioning

Author            : Anwar Jahid Ruman Hossain 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : [ LightOJ ] 1043- Triangle Partitioning
Source            : Light OJ
Category          : Searching and Sorting
Algorithm         : Bi-Section(Binary Search)
Verdict           : Accepted

1.  #include<bits/stdc++.h>  
2. using namespace std;  
3. #define ll long long int  
4. double TrianlgeRatio(double ab,double ac,double bc,double ad){  
5.     double ae,de,s1,s2,largeTriangleArea,smallTriangleArea,trapheziumArea,ratio;  
6.     ae=(ad*ac)/ab;  
7.     de=(ad*bc)/ab;  
8.   
9.     s1=(ab+ac+bc)/2.0;  
10.     s2=(ad+de+ae)/2.0;  
11.   
12.     largeTriangleArea=sqrt(s1*(s1-ab)*(s1-bc)*(s1-ac));  
13.     smallTriangleArea=sqrt(s2*(s2-ad)*(s2-de)*(s2-ae));  
14.     trapheziumArea=largeTriangleArea-smallTriangleArea;  
15.   
16.     ratio=smallTriangleArea/trapheziumArea;  
17.     return ratio;  
18. }  
19. double BiSection(double ab, double ac,double bc, double ratio){  
20.     double low,high,mid,ad;  
21.     low=0.0;  
22.     high=ab;  
23.     for(int i=0;i<100;i++){  
24.         mid=(low+high)/2.0;  
25.         ad=mid;  
26.         if(TrianlgeRatio(ab,ac,bc,ad)>ratio)  
27.             high=mid;  
28.         else low=mid;  
29.     }  
30.     return ad;  
31. }  
32. int main(){  
33.     //freopen("input.txt","r",stdin);  
34.     //freopen("output.txt","w",stdout);  
35.     int t;  
36.     cin>>t;  
37.     for(int i=1;i<=t;i++){  
38.         double ab,ac,bc,ratio,result;  
39.         cin>>ab>>ac>>bc>>ratio;  
40.         result=BiSection(ab,ac,bc,ratio);  
41.         cout<<"Case "<<i<<": "<<fixed<<setprecision(10)<<result<<endl;  
42.     }  
43.     return 0;  
44. }  
45. 
    

1. Technique: BiSection(Binary Search) 
2. Firstly , we assume a value of AD. Then we calculate ratio of ADE and BDEC(ADE/BDEC) according to our assumed value. Then we compare 
3. new calculated ratio with given ratio. To find value of AE and DE we use property of "similar triangle".Similar Triangle property is 
4. (AD/AB) = (AE/AC) = (DE/BC).As ans have to  correct upto 10^-6 fraction value, we can't say mid+1 OR mid-1 for high and low value 
5. because fraction value can be between 0.0 to 0.99(That means between 1).That's why we cant increase or decrease directy 1 from mid value 
6. of high and low.