Problem E
Planetary Grid

Yraglac wants to get around within his gated community on Mars, Cossin. The Cossin community grounds are precisely – but strangely – shaped. Yraglac has spent many hours studying the grounds and has figured out the logic behind the landscaping.

If you put the landscaper’s house on a cartesian grid at position $(0,0)$, then the height of the land at each point is equal to $h = \sin \left(\frac{\pi x}{a}\right) \cdot \cos \left(\frac{\pi y}{b} + \frac{\pi }{2}\right)$ for some $a$ and $b$ that Yraglac is still working on figuring out. Roads are laid out wherever the height is zero.

Yraglac can drive on the roads, but has to walk through any area that isn’t a road. He doesn’t like walking much, so while walking he takes the shortest possible path between an off-road point and the nearest road, breaking ties by whichever makes his driving shorter. When measuring the distance for walking between an off-road point and the road, we ignore the increase in distance caused by the height difference. In other words we only measure the distance travelled in the $xy$-plane.

Given coordinates that Yraglac wants to travel to and from, can you tell how far Yraglac will have to travel?


The input begins with an integer $1 \leq T \leq 1\, 000$, the number of test cases.

Each test case contains six integers $a$, $b$, $x_1$, $y_1$, $x_2$, and $y_2$. $a$ and $b$ ($1 \leq a,b \leq 10^8$) are the parameters to the height calculations, and $(x_1, y_1)$ and $(x_2, y_2)$ ($-10^8 \leq x_1, y_1, x_2, y_2 \leq 10^8$) are the starting and ending positions of Yraglac’s travel, respectively.

You may assume that there is a road intersecting the line segment from the starting position to the ending position.


The output consists of one number for each test case, the shortest distance Yraglac has to travel, rounded to the nearest integer.

Sample Input 1 Sample Output 1
1 1 0 0 1 1
2 2 1 1 2 2

Please log in to submit a solution to this problem

Log in