10566. Пересекающиеся лестницы

Вдоль узкой улицы по обе стороны расположены дома. Лестница длиной x футов расположена так, что ее низ упирается в основание дома на правой стороне, а верх прислонен к дому на левой стороне улицы. Аналогично низ лестницы длиной y футов упирается в основание дома на левой стороне, а верх прислонен к правому дому. Точка, в которой пересекаются лестницы, находится в точности c футов над землей. Какова ширина улицы?

Вход. Каждая строка содержит три положительных действительных числа x, y и c.

Выход. Для каждого теста вывести ширину улицы с тремя знаками после десятичной запятой.

Пример входа

30 40 10
12.619429 8.163332 3
10 10 3
10 10 1
 

Пример выхода

26.033

7.000

8.000

9.798

РЕШЕНИЕ

геометрия - бинарный поиск

Анализ алгоритма

Треугольники AOP и ADC подобны: .

Треугольники COP и CBA подобны: .

. Откуда , .

Будем искать искомую ширину улицы d = AC бинарным поиском.

Изначально положим . По имеющимся d, x, y находим a, b и c. Чем больше d (при фиксированных x, y), тем меньше c.

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

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

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

{

Установим left = 0, right = min(x,y). Далее в цикле будет иметь место неравенство left ≤ d ≤ right.

left = 0;

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

d = (left + right) / 2;

do

{

Вычисляем значения a, b, c.

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

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

Если найденное значение c1 меньше искомого с, то необходимо уменьшить верхнюю границу 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);

}