Problem G - Gopher that walks and swims

A gopher lives in the flatlands of Northern Saskatchewan and frequently visits his cousins living in the South-East part of the same province. When going on a visit the gopher has to cross a lot of ditches.

Saskatchewan has been suffering years of severe drought. Recently, however, they experienced a period of unusually heavy rains which resulted in flooding all the ditches on the gopher's route.

The ditches run along straight lines in the West-East or South-North direction and each ditch is of a constant width. The gopher still wants to make his travels but being not a very good swimmer, he wants to minimize the distance that he has to swim across the ditches. With this requirement satisfied, he also wants to walk as little as possible on the dry land. Your task is to find the length of the gopher's route which minimizes his swimming and then his walking.

We are given a system of orthogonal coordinates, where the x axis is directed from West to East and the y axis is directed from South to North. Given are positive real numbers: D and L, L+L < D, such that a point (x, y) is on dry land if and only if there exist integers m and n such that

m*D+L <= x <= (m+1)*D-L and
n*D+L <= y <= (n+1)*D-L.

Given is the starting point of the gopher (xs, ys) and its target point (xt, yt). Both these points are on dry land and also

0 < xs <= xt,
ys >= yt > 0,
xt-xs <= ys-yt.
It is also known that the gopher on his way to the target point will not have to swim through more than 300 ditches.

Each line of input contains six numbers: D, L, xs, ys, xt, yt. For each line of input, output one line with the needed information in the format shown in the sample output. The last line of input has the value of D equal to zero and this line should not be processed.

Sample input

100.0 10.0 50.0 150.0 150.0 50.0 
100.0 10.0 50.0 250.0 150.0 50.0
10.0 1.0 5 95 45 5
10.0 1.0 5 95 35 5
10.0 1.0 1.01 95 39 8.99
0 0 0 0 0 0

Output for sample input

The gopher has to swim 28.28 meters and walk 113.14 meters.
The gopher has to swim 48.28 meters and walk 183.06 meters.
The gopher has to swim 21.31 meters and walk 78.96 meters.
The gopher has to swim 20.49 meters and walk 75.89 meters.
The gopher has to swim 20.49 meters and walk 75.21 meters.

Piotr Rudnicki