Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
High-Dimensional Vector Correspondence
Time Limit: 10000MSMemory Limit: 65536K
Total Submissions: 345Accepted: 21Special Judge

Description

Let < p1, p2,..., pn > and < q1, q2,..., qn > 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 Hpi = qi 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

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator