406315: GYM102354 F Cosmic Crossroads

Consider two sets of $$$n$$$ lines passing through the point $$$(0;0;0)$$$ in Euclidean three-dimensional space. Instead of actual lines, you are given two sets, $$$2n$$$ points in each set: $$$r_i=(x_i;y_i;z_i)$$$ and $$$r_j'=(x_j';y_j';z_j')$$$. These are the points where the lines intersect the unit sphere (two opposite points for each line).

It is known that the second set was obtained from the first one by some rotation around the origin and shuffling the order of the points. You have to find a permutation $$$\pi_1, \dots, \pi_{2n}$$$ and the rotation $$$\varphi$$$ of three-dimensional space such that, for all $$$i$$$, $$$$$$|r_{\pi_i} - \varphi(r'_i)| \leq 10^{-6}\text{.}$$$$$$ The rotation $$$\varphi$$$ should be described by point $$$e=(x;y;z)$$$ and angle $$$\theta$$$. It means we rotate the space around the axis from the origin to point $$$e$$$ by angle $$$\theta$$$ following the right-hand rule (see notes).

It is guaranteed that the directions of the first set of lines were chosen uniformly at random, independently from each other.

The first line of input contains a single integer $$$n$$$ ($$$2 \leq n \leq 4 \cdot 10^4$$$).

Each of the next $$$2n$$$ lines contains three real numbers $$$x_i$$$, $$$y_i$$$ and $$$z_i$$$ describing points from the first set.

Each of the next $$$2n$$$ lines contains three real numbers $$$x'_i$$$, $$$y'_i$$$ and $$$z'_i$$$ describing points from the second set.

All real numbers are given with the precision of up to $$$12$$$ digits after decimal point.

It also holds that if point $$$r_i=(x_i;y_i;z_i)$$$ lies in one of sets then the point $$$-r_i$$$ lies in that set as well.

It is guaranteed that solution exists and would still exist even with precision of $$$10^{-9}$$$ instead of $$$10^{-6}$$$.

On the first line, print a single real number $$$\theta$$$ ($$$-\pi \leq \theta \leq \pi$$$) describing the rotation angle.

On the second line, print three real numbers $$$x$$$, $$$y$$$, $$$z$$$ ($$$10^{-3} \leq |x|+|y|+|z| \leq 10^3$$$) describing the point $$$e$$$ on the rotation axis.

On the third line, print $$$2n$$$ integers $$$\pi_1, \dots, \pi_{2n}$$$.

Assume that rotation occurs in the sense prescribed by the right-hand rule (see notes).

2
0.923879533 0.382683432 0
0.923879533 -0.382683432 0
-0.923879533 -0.382683432 0
-0.923879533 0.382683432 0
0.382683432 0.923879533 0
0.382683432 -0.923879533 0
-0.382683432 -0.923879533 0
-0.382683432 0.923879533 0

-1.570796327
0.000000000 0.000000000 1.000000000
2 3 4 1

Just so you remember, rotation is done as follows:

Example test case looks like this:

The first set of points is $$$\{1,2,3,4\}$$$, and the second set of points is $$$\{1',2',3',4'\}$$$. After the rotation of the second set of lines by $$$-\tfrac{\pi}{2}$$$ around axis $$$(0;0;1)$$$, we obtain the following matching: $$$\{(1';2),(2';3),(3';4),(4',1)\}$$$.