Amsterdam Distance

Your friend from Manhattan is visiting you in Amsterdam. She can only stay for a short while, so she wants to see as many tourist attractions as possible in as little time as possible. To plan that, she needs to know how long it takes to walk from one landmark to another. In her hometown that is easy: Manhattan is a rectangular grid of city blocks, so walking from point $m = (m_x, m_y)$ to point $n = (n_x, n_y)$ covers a distance of

$|n_x - m_x| + |n_y - m_y|$

Amsterdam is not well approximated by a rectangular grid. With its canals, Amsterdam looks much more like a half disc, with streets radiating at regular angles from the center and with canals running the arc of a circle at equally spaced intervals. A street corner is the intersection of a circular canal and a street which radiates from the city center.

Figure 1: the city model with $M = 6$, $N = 5$ and $R = 2.0$, and the shortest walk from corner $(1, 3)$ to corner $(4, 2)$.

Depending on how accurately you want to model the street plan of Amsterdam, you can split the city into more or fewer half rings and into more or fewer segments. To avoid conversion problems, the radius of the half circle is part of the input, so your program works with any unit. Write a program which computes the distance between two street corners in Amsterdam for a particular approximation.

The model is split into $M$ segments (pie slices), so $M + 1$ streets radiate from the center and the angle between two neighbouring streets is $\pi / M$. It is split into $N$ half rings, so canal $y$ has radius $R \cdot y / N$. Corner $(x, y)$ is the intersection of street $x$ and canal $y$, and street 0 and street $M$ are the two ends of the straight diameter. Canal 0 has radius 0, so every corner of the form $(x, 0)$ is the same point at the city center. You walk only along the streets and the canals.

The input consists of:

• One line with two integers $M$, $N$ and a floating point number $R$.

  • $1 \le M \le 100$ is the number of segments (or pie slices) the model of the city is split into.
  • $1 \le N \le 100$ is the number of half rings the model of the city is split into.
  • $1 \le R \le 1000$ is the radius of the city.

• One line with four integers $a_x$, $a_y$, $b_x$, $b_y$, with $0 \le a_x, b_x \le M$ and $0 \le a_y, b_y \le N$, the coordinates of two corners $a = (a_x, a_y)$ and $b = (b_x, b_y)$ in the model of Amsterdam.

Output a single line with the least distance needed to travel from corner $a$ to corner $b$ following only the streets and the canals. Round the value to nine digits after the decimal point and print all nine of them. For example, print 2.000000000 for a distance of $2$.