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
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
Given coordinates that Yraglac wants to travel to and from, can you tell how far Yraglac will have to travel?
Input
The input begins with an integer
Each test case contains six integers
You may assume that there is a road intersecting the line segment from the starting position to the ending position.
Output
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 |
---|---|
2 1 1 0 0 1 1 2 2 1 1 2 2 |
2 2 |