1506. Crossed ladders

A narrow street is lined with tall buildings. An x foot long ladder is rested at the base of the building on the right side of the street and leans on the building on the left side. An y foot long ladder is rested at the base of the building on the left side of the street and leans on the building on the right side. The point where the two ladders cross is exactly c feet from the ground. How wide is the street?

Input. Each line contains three positive real numbers giving the values of x, y and c.

Output. For each test case print one line with a real number giving the width of the street in feet, with three digits after the decimal point.

Sampe input	Sample output
30 40 10 12.619429 8.163332 3 10 10 3 10 10 1	26.033 7.000 8.000 9.798

SOLUTION

geometry – binary search

Algorithm analysis

Triangles AOP and ADC are similar: .

Triangles COP and CBA are similar: .

. Whence , .

We’ll search for the required street width d = AC with binary search.

Initially set 0 ≤ d ≤ min(x, y). Given d, x, y find a, b and c. The larger d (with fixed x, y), the smaller c.

Algorithm realization

Read the input data for each test case.

while(scanf("%lf %lf %lf",&x,&y,&c) == 3)

{

Set left = 0, right = min(x,y). Further in the while loop, holds the inequality left ≤ d ≤ right.

left = 0;

if (x < y) right = x; else right = y;

d = (left + right) / 2;

do

{

Compute the values of a, b, c.

a = sqrt(x*x - d*d); b = sqrt(y*y - d*d);

c1 = 1/(1/a + 1/b);

If the found value of c1 is less than the desired c, then it is necessary to reduce the upper bound d. Otherwise, you should increase its lower bound.

if (c1 < c) right = (left + right) / 2;

else left = (left + right) / 2;

d = (left + right) / 2;

Carry out the calculations to the accuracy required in the problem statement (four decimal digits).

} while (fabs(c1 - c) > 0.00001);

Print the answer.

printf("%.3lf\n",d);

}

Java realization

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

con.useLocale(new Locale("US"));

while(con.hasNext())

{

double x = con.nextDouble();

double y = con.nextDouble();

double c = con.nextDouble();

double Left = 0, Right, a, b, c1;

if (x < y) Right = x; else Right = y;

double d = (Left + Right) / 2;

do

{

a = Math.sqrt(x*x - d*d);

b = Math.sqrt(y*y - d*d);

c1 = 1/(1/a + 1/b);

if (c1 < c) Right = (Left + Right) / 2;

else Left = (Left + Right) / 2;

d = (Left + Right) / 2;

} while (Math.abs(c1 - c) > 0.00001);

System.out.format(Locale.US,"%.3f\n",d);

}

}

}