Bee on the Honeycomb

Time limit1sMemory limit128 MB

Summary

Given hexagonal tiling with side s and two points A and B, find the minimum-length path that goes from A to its hexagon center, hops between adjacent centers, then reaches B.

Level: Medium7 of 10
Topics: Geometry, Math, Shortest path, Implementation
Solved: No attempts yet

Problem

Imagine a perfectly regular honeycomb that tiles the entire infinite Cartesian plane: an interlocking grid of congruent regular hexagons. One hexagon is placed so that its center is at the origin and two of its opposite corners lie on the $x$ -axis, so every hexagon has a flat top edge and a flat bottom edge with pointed left and right corners. The side length of the hexagons is given.

To avoid getting lost, a bee always travels from a point A to a point B by the same rule:

From A it flies straight to the exact center of the hexagon that contains A.
From that center it flies in a straight line to the center of an adjacent hexagon, and it keeps hopping from one center to the center of a neighboring hexagon until it reaches the hexagon that contains B.
From the center of that final hexagon it flies straight to B.

Among all routes allowed by this rule the bee takes one of minimum total length. If A and B already lie in the same hexagon, the bee simply flies straight from A to B without visiting any center.

The figure below shows one such minimum-length route from A to B.

Input

Each data set is one line containing 5 floating-point numbers. The first number is the side length of the hexagons, in centimeters. The next two numbers are the $x$ and $y$ coordinates of point A, and the last two are the $x$ and $y$ coordinates of point B. Neither A nor B ever lies exactly on a border between two hexagons. The input ends with a line of five zeroes, which is not processed.

Output

For each data set, print on its own line the minimum length of the bee's path from A to B, in centimeters, rounded to the nearest $0.001$ centimeter (exactly three digits after the decimal point).

Examples4

Example 1

Input

1.0 -3.2 2.2 3.3 0
9 1 4 5 1
0.1 .09 0 .21 0
0 0 0 0 0

Expected output

7.737
5.000
0.526

Example 2
Input
```
10 1 1 2 -1
0 0 0 0 0
```
Expected output
```
2.236
```

Example 3

Input

2.0 0 0 3.0 1.732050808
0 0 0 0 0

Expected output

3.464

Example 4

Input

1.0 0 0 4.5 2.598076211
0 0 0 0 0

Expected output

5.196