CCPC 2017 Open Contest


2017-03-18 20:00 CET

CCPC 2017 Open Contest


2017-03-19 00:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -185 days 15:57:42

Time elapsed


Time remaining


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.

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