[ UVa - 10566 & LightOJ 1062 ] - Crossed Ladders [ Tutorial with Bisection Methos & Solution ]

=>Try Yourself First. For help Scroll Down.

Hi There !!! Crossed Ladders Problem - A very well-known, interesting, and easy to solve problem ( If your observation is Good ). In this post, I am showing you a very easy way to solve this problem. In this post, you also will get some Basic points about Geometry that will help to solve your problem and make your Knowledge Clarify about this problem. So, here we go. 

Problem Clarification : 

A ladder with length X rested from the Base & lean with the Right Building. Another ladder with length Y rested from another Right side's Base & lean with the Left side's Base. These two ladders are crossed at a point ( N ). The length between base M & N is ' h '. We have to find the Width of the Road. 

Theory :   

Do You know the Similar Right Triangle ? ? At first watch the picture :

Courtesy: Admin Zero.

In the Crossed Ladder Problem two ladder AC & BD is Crossed each other at point N. The length of AC & BD is X & Y respectively. You are also given the value of length 'h'.  On the other hand let's denote Ab = h1 , CD = h2, AD = d  . From these Values, we will find out the value of d. It's very clear that the value of d will always be less than the Values X & Y. You have to process Bisection in this length which will help you to find the Correct Result. 

From the Theory Crossed Ladder problem we can say that , 

1/h1 + 1/h2 = 1/h

To understand how this Equation Comes watch the Pictures Next ..... These pictures will show you the proof for Similar Right Triangle.

Special Thanks: Riasat Ali Akash

Hence We have the proof. Let's go solve the problem. 

We have found our main Function. Now from low = d = 0 to high = d = minimum(X, Y) we can do the Bisection . Every time we have to find the Mid value between low & high. 

An awesome characteristic that lies in the Crossed Ladder problem is when the Width d increases the Height h decreases and vice versa. That means from several Mid values of width we just have found such a value that will fairly equal to h.  But how ??

Let the mid = K ( in general d ) & you have the value of  X. From the Pythagorean theorem, We know,

(hypotenuse)^2= (base)^2 + (perpendicular)^2

From this equation, We can show that...

h1 = sqrt((y*y) - (mid*mid))

h2 = sqrt((x*x) - (mid*mid))

So now you have the value of h1 & h2 . You can easily find ,

h = ( h1 * h2 ) / ( h1 + h2 )

For a value of mid, we will found the approximate value of real h. Now for every h, you easily can compare with the Correct h. 

That's how you can solve this problem.

Code:

#include <bits/stdc++.h>
#define DIST(x1,x2, y1, y2) (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)))
#define CLR(a) a.clear()
#define VCLR(a, n) for(int i=0; i<=n+3; i++) a[i].clear()
#define SIZE(a) a.size()
#define ERASE(a, b) memset(a, b, sizeof a)
#define PB(a, b) a.push_back(b)
#define PB2(a,i,b) a[i].push_back(b)
#define LL long long
#define DBG cout<<"I Am Here"<
#define MAX 600005
#define CASE(i) printf("Case %d: ", i);
#define PI acos(-1)
#define EPS 0.00000001

using namespace std;

double x, y, c;

double solve(double mid)
{
    double A = sqrt((x*x) - (mid*mid));
    double B = sqrt((y*y) - (mid*mid));
    return ((A*B)/(A+B));
}

int main()
{
    int test;
    
    while(scanf("%lf %lf %lf", &x, &y, &c)==3)
    {
        double lo = 0.0, hi = min(x, y), mid;

        int cnt = 100;
        double ans = 1;
        while(cnt--)
        {
            mid = (lo + hi)/2.0;
            
            if(solve(mid)<=c)
            {
                hi = mid;
            }
            else
            {
                lo = mid;
            }
        }
        printf("%0.3lf\n",lo);
    }
    return 0;
}

=>Question or Need Help ?? Leave a Comment.