Лазерный выстрел
Вы — дроид, и ваша задача — попытаться поразить Джедая в комнате. Известно, что Джедай может блокировать лазер своим световым мечом, поэтому прямой выстрел не сработает. Однако, если вы выстрелите двумя лазерами так, чтобы они одновременно достигли его с разных углов, он не сможет заблокировать оба. К счастью, комната (квадратная) зеркальная, что позволяет отражать лазерные выстрелы от стен. Однако зеркала не идеальны, и каждый лазер может отразиться ограниченное число раз, прежде чем рассеется.
Как дроид, у вас есть и другие задачи, поэтому вы хотите минимизировать время между выстрелами двух лазеров. У вас есть два лазерных пистолета и дроидные рефлексы, что позволяет стрелять с произвольно малым интервалом (включая одновременный выстрел).
Комната — это квадрат со стороной 1000000 футов. Ее нижний левый угол находится в точке (0, 0), а верхний правый — в точке (1000000, 1000000). Вы находитесь в точке (x_1, y_1), а Джедай — в точке (x_2, y_2). Лазер, отразившись и пройдя через (x_1, y_1), продолжает свой путь (вы предусмотрели это и можете уклониться), но лазер останавливается, как только достигает (x_2, y_2). Лазер, попавший в стену, отражается по обычным правилам (угол падения равен углу отражения, и отражение не вызывает задержки). Лазер, попавший прямо в угол, отразится в противоположном направлении и будет считаться, что он отразился дважды. Для простоты предположим, что скорость света (и лазера) равна 1 футу за наносекунду.
Входные данные
Каждый тестовый случай состоит из одной строки из 5 целых чисел, разделенных пробелами: x_1, y_1, x_2, y_2, n, где x_1, y_1, x_2 и y_2 описаны выше, а n — это максимальное количество отражений. 1 ≤ x_1, y_1, x_2, y_2 ≤ 999999, и 1 ≤ n ≤ 100. Гарантируется, что дроид и Джедай не находятся в одном месте, т.е. (x_1, y_1) ≠ (x_2, y_2). Последний тестовый случай сопровождается "0 0 0 0 0", который не должен обрабатываться.
Выходные данные
Для каждого тестового случая выведите в одной строке минимальную задержку между выстрелами лазеров в наносекундах, с точностью до 5 знаков после запятой. Обратите внимание, что тестовые данные сконструированы так, чтобы ни один из ответов не находился в пределах 1e-6 от границы округления.
