Teleportation Optimization in Park and Map

Mio loves a famous fact from mathematics: if you drop a map completely inside a park, there exists a point on the map that exactly overlays the point it represents in the park. In this problem the park is represented by a rectangle P and the map is another rectangle M (which is smaller or equal in size) that is similar to P.

The map is defined formally by a positive real number \(r\) and an affine bijective function \(f: M \to P\) satisfying

[ \frac{|f(a)-f(b)|}{|a-b|} = r \quad\text{for every two distinct points } a,b \in M. ]

Since (f) is a similarity transformation, it has a fixed point (p_0) such that

[ f(p_0) = p_0. ]

Mio can move in two different ways:

1. Walking: She can walk at a speed of 1 unit per second. When walking in the park, distances are measured in the park's coordinate system. When walking on the map, distances are measured in the map's coordinate system.
2. Teleportation: When Mio is at some point x in one domain (including the boundary), she may teleport to the corresponding point in the other domain. Specifically, if she is on the map at point x, she can teleport to f(x) in the park; if she is in the park at point y, she can teleport to f^-1(y) on the map. Each teleportation takes exactly k seconds. Mio can teleport at most n times.

Note that due to the fixed point property, there is always at least one point \(p_0\) which lies in both domains simultaneously, meaning that if Mio reaches \(p_0\), she is effectively at the same point in both the park and the map.

You are given two points s and t in the park. Mio starts at s (in the park) and wants to reach t (in the park) in minimum time. Determine the minimum time required, assuming that when a teleportation is used, the transformation follows the fixed similarity \(f(x) = p_0 + r(x-p_0)\).

Crucial Observation:

Since \(f(x)=p_0+r(x-p_0)\), for any point \(x\) in the park, its corresponding point on the map is

[ f^{-1}(x)=p_0+\frac{x-p_0}{r}. ]

This implies that if Mio is at point \(x\) (with distance \(d(x,p_0)\) from \(p_0\)) in the park and teleports to the map, she lands at a point which is at distance \(d(x,p_0)/r\) from \(p_0\); conversely, teleporting from the map brings her to a point at distance \(r\) times her current distance from \(p_0\) in the map.

A direct consequence is that the only potentially useful teleportation is the paired teleportation from park to map and then from map back to park. Observe that:

• If Mio goes directly by walking from s to t in the park, the time cost is the Euclidean distance \(d(s,t)\).
• If she uses one pair of teleports (which costs \(2k\) seconds total), then she can effectively travel from s to t with a walking time of \(d(s,t)/r\) (because \( f^{-1}(s)=p_0+\frac{s-p_0}{r} \) and \( f^{-1}(t)=p_0+\frac{t-p_0}{r} \), so the walking distance on the map is \(d(f^{-1}(s),f^{-1}(t))=\frac{d(s,t)}{r}\)). Hence, the total time using one teleportation pair is \(\frac{d(s,t)}{r}+2k\).

Since the map is a smaller (or equal) version of the park, we have \(r \le 1\) in a typical setting. Therefore, when \(r \le 1\), \(\frac{d(s,t)}{r}+2k \ge d(s,t)\), and direct walking is always optimal. However, if \(r > 1\) and at least two teleportations are available (i.e. n ≥ 2), then the paired teleportation yields a time of \(\frac{d(s,t)}{r}+2k\); in this case the answer is the minimum between direct walking and using a teleport pair. Note that even if more than two teleportations are allowed, using more than one pair never improves the time further.

Input Format:

The input consists of three lines:

• The first line contains three numbers: an integer n (the maximum number of teleportations), a real number k (the time cost for each teleportation), and a real number r (the similarity ratio in the transformation \(f\)).
• The second line contains two real numbers s_x and s_y, the coordinates of the starting point s in the park.
• The third line contains two real numbers t_x and t_y, the coordinates of the target point t in the park.

Output Format:

Output a single number: the minimum time required for Mio to reach point t from s. The answer should be printed with 6 decimal places of precision.

Note: Mio starts in the park. Teleportation is only possible if at least a pair can be performed (i.e. if n ≥ 2). Thus, the final answer is computed as follows:

• If n < 2, then answer = \(d(s,t)\).
• If n ≥ 2 and \(r > 1\), then answer = min\(\{d(s,t),\ \frac{d(s,t)}{r}+2k\}\).
• Otherwise (if r \le 1), direct walking is optimal and answer = \(d(s,t)\).

Here, \(d(s,t)\) denotes the Euclidean distance between s and t.

inputFormat

The input consists of three lines:

• Line 1: n k r where n is an integer (0 ≤ n ≤ 10⁹), k and r are real numbers. It is guaranteed that r > 0.
• Line 2: s_x s_y representing the coordinates of the start point s.
• Line 3: t_x t_y representing the coordinates of the target point t.

All numbers are separated by spaces.

outputFormat

Output a single real number: the minimum time required to go from s to t. Print the result with 6 decimal places.

sample

0 1 2
0 0
10 0

10.000000