Евклидово TSP
Знаменитый алгоритм аппроксимации Ароры-Митчелла для евклидовой задачи коммивояжера (евклидоваTSP) был открыт независимо Санджевой Аророй и Джозефом С. Б. Митчеллом в 1998 г. Он может приблизительно вычислить значение оптимального пути TSP в измерении d в пределах временного коэффициента 1 + 1 / c.
где n - количество вершин в пути.
Мирослава работает в компании компьютерной безопасности, и настало время обновить общий криптографический ключ во многих центрах обработки данных по всей Европе. Для этого Мирослава собирается арендовать частный самолет и предоставить ключ сотрудникам, ожидающим его во всех крупных европейских аэропортах. Она хочет вернуться как можно скорее.
У компании Мирославы есть компьютер, способный выполнять p миллиардов операций в секунду. Поскольку мы можем аппроксимировать Европу двумерной плоскостью, то предполагаем, что алгоритм Ароры-Митчелла работает точно
секунд на этом компьютере для получения точной (1 + 1 / c) - аппроксимации оптимального маршрута.
Мирослава заметила, что c является параметром алгоритма, который может быть ей полезен, однако следует быть очень осторожным при выборе правильного его значения. Если она возьмет слишком малым значение c, то алгоритм завершится очень быстро, а время, которое она проведет в Европе, будет слишком велико. С другой стороны, установка слишком высокого значения заставит ее ждать ответа от компьютера, в то время как она может летать в это время.
Мирослава раньше работала в другой компании, и оттуда она знает, что длина оптимального тура по всем крупным европейским аэропортам занимает с метров, однако она не имела достаточно высокого положения в компании, чтобы знать фактический тур. Учитывая скорость v частного самолета в метрах в секунду, Мирославе требуется s * (1 + 1 / c ) / v секунд для завершения тура, созданного алгоритмом, запущенным с параметром c. Для простоты мы предполагаем, что Мирослава может приземлиться, оставить копию личного ключа и вылететь из каждого аэропорта в одно мгновение.
Сколько времени займет у Мирославы чтобы сначала запустить алгоритм, а затем распределить все ключи, предполагая, что она выбирает оптимальный параметр c?
Входные данные
Строка содержит четыре числа:
число n (4 ≤ n ≤
10^6) - количество аэропортов;действительное число p (0.001 ≤ p ≤ 5000) - количество миллиардов операций, которое может выполнять компьютер в секунду;
действительное число s (
10^6≤ s ≤10^9) - длина оптимального тура по европейским аєропортам в метрах;действительное число v (50 ≤ v ≤ 900) - скорость частного самолета в метрах в секунду.
Все действительные числа содержат не более 10 десятичных цифр.
Выходные данные
Выведите в одной строке минимально возможное время t в секундах для распределения ключей и значение параметра c, которое Мирослава должна использовать для достижения времени t. Ваш ответ должен иметь абсолютную или относительную ошибку не более 10^(-6).