ZOJ Problem Set - 3945
Carl the ant is our old friend. In 2004, he was a little mixed-up and always taking strange paths, and in 2009, he had straightened his life and started to take the shortest path between any pair of points. But now, he travels to a novel place, and it's not easy for him to choose the shortest path. Can you help him?
The place is considered as an infinite three-dimensional space divided into grids. Some of them are black and the others are white. The black girds represent the land of the world and the white grids represent the air.
Obviously, Carl can only walk on the surface (including edge or vertex) of black grids. Luckily, the grids are regular. Every black grid shares common vertex with exact 8 other black grids and has no common edges or faces with these black grids. The following picture shows a fraction of the grid world:
Now, we place the center of one black grid on the origin and the edge of the grids are paralleled with axes. Also, we assume that every edge is exactly 1cm long. Carl has told you his starting point and the destination point, help him to calculate the distance of the shortest path between them.
There are multiple test cases. The first line of input is an integer T indicating the number of test cases. For each test case:
The only line contains 6 numbers X1, Y1, Z1, X2, Y2 and Z2 (-104 ≤ X1, Y1, Z1, X2, Y2, Z2 ≤ 104), representing the coordinates of the starting point and the destination point. It is guaranteed that both points are on the surface of black grid.
For each case, output the length in centimeters of the shortest path from the starting point to the destination point. Absolute error or relative error less than 10-8 will be accepted.
3 0.5 0.5 0.5 0.5 -0.5 -0.5 -0.5 -0.5 -0.5 1.5 1.5 1.5 0.4 0.3 0.5 0.6 0.5 0.7
1.4142135623730950488016887242097 4.4721359549995793928183473374626 0.4472135954999579392818347337462
For the first sample, the starting point and the destination point are on the same surface so just go straight there.
For the second sample, Carl can go to (0.5, 0.5, 0.5) first and then go to the destination point.
For the third sample, Carl can also go to (0.5, 0.5, 0.5) first and then go to the destination point.
Author: JIN, Mengge
Source: The 13th Zhejiang Provincial Collegiate Programming Contest