Схрещені драбини#1506

Схрещені драбини (Розбір)

Трикутники $A O P$ і $A D C$ подібні: $\frac{c}{b} = \frac{A P}{A C}$ \frac{c}{b} = \frac{AP}{AC}

Трикутники $C O P$ і $C B A$ подібні: $\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

Звідки

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}

Будемо шукати ширину вулиці $d = A C$ d = AC методом бінарного пошуку.

Спочатку покладемо $0 \leq d \leq min (x, y)$ 0 \le d \le min(x, y). Знаючи значення $d, x$ та $y$ , можна обчислити $a, b$ і $c$ . При фіксованих $x$ та $y$ зі збільшенням $d$ величина $c$ зменшується.

Реалізація алгоритму

Читаємо вхідні дані для кожного тесту.

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

Установимо значення: $l e f t = 0, r i g h t = min (x, y)$ left = 0, right = min(x,y). Далі в процесі виконання циклу завжди виконується нерівність $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
  {

Обчислюємо значення $a, b, c$ a, b, c.

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

Якщо обчислене значення $c 1$ менше заданого $с$ , необхідно зменшити верхню межу $d$ . В іншому випадку слід збільшити нижню межу.

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

Обчислення виконуються до досягнення необхідної у задачі точності — чотирьох десяткових знаків.

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

Виводимо результат.

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

Java реалізація

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++