Similar Rotations
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 21 Accepted Submission(s): 0
Problem 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.
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