Crossed Ladders#1506

Crossed Ladders (Editorial)

The tiangles $A O P$ and $A D C$ are similar: $\frac{c}{b} = \frac{A P}{A C}$ \frac{c}{b} = \frac{AP}{AC}

The tiangles $C O P$ and $C B A$ are also similar: $\frac{c}{a} = \frac{C P}{C A}$ \frac{c}{a} = \frac{CP}{CA}

\frac{c}{b} + \frac{c}{a} = \frac{A P}{A C} + \frac{C P}{A C} = \frac{A C}{A C} = 1

\frac{c}{b} + \frac{c}{a} = \frac{AP}{AC} + \frac{CP}{AC} = \frac{AC}{AC} = 1

Whence

c (\frac{1}{a} + \frac{1}{b}) = 1, c = \frac{1}{\frac{1}{a} + \frac{1}{b}} = \frac{ab}{a + b}

c \left( \frac{1}{a} + \frac{1}{b} \right) = 1, c = \frac{1}{\frac{1}{a} + \frac{1}{b}} = \frac{ab}{a + b}

We’ll find the width of the street $d = A C$ d = AC using the binary search method.

Initially, let $0 \leq d \leq min (x, y)$ 0 \le d \le min(x, y). Given the values of $d, x$ and $y$ , we can compute $a, b$ and $c$ . For fixed $x$ and $y$ as $d$ increases, the value of $c$ decreases.

Algorithm implementation

Read the input data for each test case.

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

Set the initial values: $l e f t = 0, r i g h t = min (x, y)$ left = 0, right = min(x,y). During the execution of the loop, the inequality $l e f t \leq d \leq r i g h t$ left \le d \le right.

  left = 0;
  if (x < y) right = x; else right = y;
  d = (left + right) / 2;
  do
  {

Compute the values of $a, b, c$ a, b, c.

    a = sqrt(x*x - d*d); b = sqrt(y*y - d*d);
    c1 = 1/(1/a + 1/b);

If the computed value $c 1$ is less than the given $с$ , the upper bound of $d$ should be decreased. Otherwise, the lower bound should be increased.

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

The computations are performed until the required accuracy specified in the problem statement is reached — four decimal places.

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

Print the answer.

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

Java implementation

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);
    }
  }
}

C++