3707 -- High-Dimensional Vector Correspondence

Language:

High-Dimensional Vector Correspondence

Time Limit: 10000MS		Memory Limit: 65536K
Total Submissions: 365		Accepted: 22		Special Judge

Description

Let < p₁, p₂,..., p_n > and < q₁, q₂,..., q_n > be two sequences of vectors in the m-dimensional Euclidean space. Is that possible to transform the former using a series of reflections and/or rotations so that it becomes the latter?

Input

The input consists of a single data set given in the format (n, m ≤ 512)

$\begin{tabular}{cccc} \textit{m} & \textit{n} & & \\ \textit{p}$_{11}$ & \textit{p}$_{12}$ & $\cdots$ & \textit{p}$_{1m}$ \\ \textit{p}$_{21}$ & \textit{p}$_{22}$ & $\cdots$ & \textit{p}$_{2m}$ \\ $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ \\ \textit{p}$_{n1}$ & \textit{p}$_{n2}$ & $\cdots$ & \textit{p}$_{nm}$ \\ \textit{q}$_{11}$ & \textit{q}$_{12}$ & $\cdots$ & \textit{q}$_{1m}$ \\ \textit{q}$_{21}$ & \textit{q}$_{22}$ & $\cdots$ & \textit{q}$_{2m}$ \\ $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ \\ \textit{q}$_{n1}$ & \textit{q}$_{n2}$ & $\cdots$ & \textit{q}$_{nm}$\\ \end{tabular}$

where

$\begin{tabular}{c} \textit{\textbf{p}}$_i$=[\textit{p}$_{11}$\quad\textit{p}$_{12}$\quad $\cdots$\quad\textit{p}$_{1m}$]\textsuperscript{T} \\ \textit{\textbf{q}}$_i$=[\textit{q}$_{11}$\quad\textit{q}$_{12}$\quad $\cdots$\quad\textit{q}$_{1m}$]\textsuperscript{T} \\ \end{tabular}$
for all 1≤i≤n. All numbers except m and n are floating-point. Blank characters are irrevelant.

Output

It is known that both reflections and rotations are linear transformations, which are represented by squarematrices. In particular, in the m-dimensional Euclidean space, they are represented by m × m matrices. Furthermore, composition of linear transformations is represented by the product of the corresponding matrices. Therefore, if the desire sequence of reflections and rotations exists, you are to output a matrix H in the format

$\begin{tabular}{cccc} \textit{m} & & & \\ \textit{h}$_{11}$ & \textit{h}$_{12}$ & $\cdots$ & \textit{h}$_{1m}$ \\ \textit{h}$_{21}$ & \textit{h}$_{22}$ & $\cdots$ & \textit{h}$_{2m}$ \\ $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ \\ \textit{h}$_{m1}$ & \textit{h}$_{m2}$ & $\cdots$ & \textit{h}$_{mm}$ \\ \end{tabular}$

such that Hp_i = q_i for all 1≤i≤n; otherwise, you only have to output an asterisk ("*"). Blank characters are irrevelant.

Sample Input

2 2
-0.923896909208131 -0.150594719880319
-3.269301773087776E-002 0.871630392603206
0.402113583440769 -0.845321793468377
0.735234663492202 0.469295604408862

Sample Output

2
-0.569248928113214700 0.822165225390831260 
0.822165225390831590 0.569248928113214810

Source

POJ Founder Monthly Contest – 2008.12.28, frkstyc