10773. Назад к математике средней школы

Необходимо пересечь реку длиной d метров. Скорость течения реки v м/с, скорость лодки u м/с. Существует возможность пересечь реку либо за минимальное время, либо по кратчайшему пути (пути, перпендикулярному течению реки). Если существуют такие два разные пути, то вывести неотрицательную разницу времен их преодоления с тремя точками после запятой. Иначе вывести фразу “can’t determine”.

Вход. Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит три числа d, v, u (v, u ³ 0, d > 0).

Выход. Для каждого теста вывести в отдельной строке его номер, а также искомую положительную разницу времен, если между берегами реки существует два разных пути, или фразу “can’t determine” иначе.

Пример входа

3

8 5 6

1 2 3

1 5 6

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

Case 1: 1.079

Case 2: 0.114

Case 3: 0.135

РЕШЕНИЕ

математика

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

Если направить вектор скорости лодки перпендикулярно течению реки, то достичь второго берега можно за минимальное время. В этом случае течение реки будет сносить лодку, однако скорость ее приближения к противоположному берегу будет максимально возможной и равной u м/с. Время пересечения реки равно d / u. В случае движения по кратчайшему пути лодку следует направить таким образом, чтобы равнодействующая ее скорости и скорости течения была направлена перпендикулярна течению реки. Тогда скорость приближения к берегу равна и время пересечения реки равно d /

Два пути совпадут, если скорость реки равна 0, в этом случае необходимо вывести фразу “can’t determine”. Эту фразу следует также вывести, если скорость течения не меньше скорости лодки (v ³ u). Если скорость лодки равна нулю (u = 0), то неравенство v ³ u справедливо при любом v.

Пример

Рассмотрим входные данные для первого теста. Время пересечения реки за кратчайшее время равно 8 / 6 = 1.3333. Скорость приближения к берегу в случае движения по кратчайшему пути равно , время преодоления реки – 8 / = 2.4121. Разность вычисленных времен с округлением до трех знаков после запятой равна 1.079.

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

Читаем входные данные и проверяем условия, при которых не существует двух разных путей. Переменная q содержит номер текущего теста.

scanf("%d",&tests);

for(q = 1; q <= tests; q++)

{

scanf("%lf %lf %lf",&d,&v,&u);

if ((v >= u) || (v == 0.0))

{

printf("Case %d: can't determine\n",q);

continue;

}

Переменной t1 присваиваем кратчайшее время переправы, переменной t2 – время переправы по кратчайшему пути. Находим их разность с учетом того, что t2 ³ t1 и печатаем результат с тремя точками после запятой.

t1 = d / u;

t2 = d / sqrt(u * u - v * v);

res = t2 - t1;

printf("Case %d: %.3lf\n",q,res);

}