Light OJ 1043 – Triangle Partitioning [solved]

Posted on February 4, 2019 by Mobarak Hosen Shakil — Leave a comment

This problem can be solved using Binary Search. But I’ve found a one line solution using Basic Geometry. You can try to solve using using Binary Search. To learn Binary Search you can go through this way: Binary Search

Explanation:

Theorem-1: If two triangles are equiangular, then their matching sides are also proportional.

Theorem-2: The ratio of the areas of two similar triangles is equal to the ratio of the squares on any two matching sides.

From Theorem-1, we can write:

$\dfrac{AD}{AB} = \dfrac{AE}{AC} = \dfrac{DE}{BC}$

and therefore, $\bigtriangleup ABC \cong \bigtriangleup ADE$ .

From Theorem-2: we can write:

$\dfrac{\bigtriangleup ADE}{\bigtriangleup ABC} = \dfrac{DE^{2}}{BC^{2}}$ ;
$\dfrac{\bigtriangleup ADE}{\bigtriangleup ABC} = \dfrac{AD^{2}}{AB^{2}}$

Let, Area of ADE = m and Area of BDEC = n, so Area of ABC = m+n;

Then, AD = sqrt(m/(m+n)) * AB;

Optimized Code:

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: https://iuconvergent.wordpress.com
*******************************************/

#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
#define LL long long int
#define ULL unsigned LL

const int inf=1<<30;
const LL INF=1e18;
const int MOD=1e9+7;


int main()
{
    int tn, cn=0;
    scanf("%d", &tn);
    while(tn--)
    {
        double ab, ac, bc, r;
        scanf("%lf%lf%lf%lf", &ab, &ac, &bc, &r);

        double ad = sqrt(r/(r+1))*ab;
        printf("Case %d: %.10lf\n", ++cn, ad);
    }
    return 0;
}