Euclidean TSP

Sanjeev Arora and Joseph S. B. Mitchell discovered the Arora-Mitchell approximation algorithm for the Euclidean travelling salesman problem independently in 1998. In $d$ dimensions it approximates the length of an optimal tour within a factor of $1 + 1/c$, and it runs in time

$n\left(\log n\right)^{O\left(\left(c\sqrt{d}\right)^{d-1}\right)}$

where $n$ is the number of nodes in the tour.

Miroslava works for a computer security company, and the shared cryptographic key of many data centres across Europe is due for renewal. She rents a private jet and delivers the key to employees waiting at every major European airport. She wants to be back as soon as possible.

Her company has a computer that executes $p \cdot 10^{9}$ operations per second. Europe is approximated by a two-dimensional plane, so on that computer the algorithm runs for exactly

$\frac{n\left(\log_{2} n\right)^{c\sqrt{2}}}{p \cdot 10^{9}}$

seconds and produces the $(1 + 1/c)$-approximation of the optimal tour.

The parameter $c$ is Miroslava's to choose, and both extremes hurt her. A small $c$ makes the algorithm finish quickly but leaves a long tour to fly. A large $c$ shortens the tour but keeps her waiting in front of the computer.

From a previous job Miroslava knows that the optimal tour of all major European airports is $s$ meters long, but she was not ranked high enough to learn the tour itself. The jet flies at $v$ meters per second, so flying the tour that the algorithm produces with parameter $c$ takes $s(1 + 1/c)/v$ seconds. Landing, leaving a copy of the key and taking off again take no time at all.

Compute how long it takes Miroslava to first run the algorithm and then distribute all the keys, assuming she chooses the parameter $c$ that minimizes the total time.

One line with four numbers:

• an integer $n$ ($4 \le n \le 10^{6}$), the number of airports;
• a real number $p$ ($0.001 \le p \le 5000$), the number of billions of operations the computer executes per second;
• a real number $s$ ($10^{6} \le s \le 10^{9}$), the length of the optimal tour of all European airports in meters;
• a real number $v$ ($50 \le v \le 900$), the speed of the private jet in meters per second.

Every real number has at most 10 digits after the decimal point.

Print on one line the shortest possible time $t$ in seconds needed to distribute the keys, then the parameter $c$ that achieves it, separated by one space. Print both numbers rounded to exactly 6 digits after the decimal point.

The total time is strictly convex in $c$ for $c > 0$, so the minimum and the parameter that attains it are unique.