Similar Rotations

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

In mathematics especially in Euclidean geometry, we often notice rotations and corresponding rotation matrices. The dimension of the whole space of three dimensional rotation matrices is three. A natural problem is, how to measure the space. It is no doubt that the space is a metirc space if we measure the distance of two rotations as the maximum distance of two images for a point on the unit sphere.
We define the distance dist(p,q) of two points p, q on the unit sphere as the length of shortest path along the surface of unit sphere. For each two rotations $R_1$ and $R_2$ one can find the point p on the unit sphere with the largest $L_{R_1,R_2}$ = dist$(R_1(p),R_2(p))$.We define $L_{R_1,R_2}$ as the distance of rotations $R_1$ and $R_2$.
Here we have several three dimensional rotation matrices. For each one of them, please find another one of them with the shortest distance to it in this metric space.

Input

There are no more than 100 cases. For each case, the first line consists an integer n (1 ≤ n ≤ 100), which is the number of rotation matrics. Each of the following n lines consists 9 float-point numbers R(0,0),R(0,1),R(0,2),R(1,0),R(1,1),R(1,2),R(2,0),R(2,1),R(2,2) with six decimal places corresponding to the a rotation matrix R.

Output

For each test case, output one line with n float-point numbers. The i-th one is the shortest distance to the i-th rotation from another one of them. The answer should be rounded to two decimal places

Sample Input

4 1.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 -1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 0.000000 0.000000 -1.000000 -0.000000 0.000000 0.000000 -1.000000 1.000000 0.000000 0.000000 0.000000 -0.000000 1.000000 0.000000 -1.000000 -0.000000 4 1.000000 0.000000 0.000000 0.000000 0.000000 -1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 0.000000 0.000000 -0.707107 -0.707107 0.000000 0.707107 -0.707107 1.000000 0.000000 0.000000 0.000000 -1.000000 -0.000000 0.000000 0.000000 -1.000000 1.000000 0.000000 0.000000 0.000000 -0.000000 1.000000 0.000000 -1.000000 -0.000000

Sample Output

1.57 1.57 1.57 1.57 0.79 0.79 0.79 1.57

Hint

jiangzijing2015

Source

2016ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

提交代码