
ZOJ Problem Set  3945
Carl the ant is our old friend. In 2004, he was a little mixedup 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 threedimensional 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. InputThere 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 X_{1}, Y_{1}, Z_{1}, X_{2}, Y_{2} and Z_{2} (10^{4} ≤ X_{1}, Y_{1}, Z_{1}, X_{2}, Y_{2}, Z_{2} ≤ 10^{4}), representing the coordinates of the starting point and the destination point. It is guaranteed that both points are on the surface of black grid. OutputFor 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. Sample Input3 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 Sample Output1.4142135623730950488016887242097 4.4721359549995793928183473374626 0.4472135954999579392818347337462 HintFor 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 