题目居然把我写的那提示都省了，本不想考大家知不知道旋转和反射怎么用矩阵表示的，真是无奈。

如果诸位不怕折腾，那么就去搞旋转吧。具体我是不愿意去想了，大致说来就是这个样子：

高维的循环可以表示成 PGP'，其中 P 是一个正交矩阵，G 是一个 Givens 旋转。有了这个形式之
后，就设法找一堆 P，对应找一堆 G，转啊转的也许就好了，也许还没好（有时候反射是必须的）。也
许不难，但是细节别问我，从一开始就没考虑过这么做。

单用反射就可以解决问题了。方法也很直观，先弄一下把 p_1 和 q_1 对起来，再弄一下把 p_2 和
q_2 对起来，反复直到全部都对起来。如果实例是可解的，那么在把 p_1, p_2, …, p_{k-1} 和
q_1, q_2, …, q_{k-1} 对起来之后，弄 p_k 和 q_k 的时候是不会把前面已经弄好的又弄坏
的（证明不难，自己去想）。反射的矩阵表示是 I-2uu'，其中 u 是沿法线方向的单位矢量。剩下的
事情就是把每个反射都表示成矩阵然后都乘起来就得到 H 了。只要其中有任何一步出问题，那就是无解
啰。

Checker 主要就检查两个事情：HP=Q 和 H'H=I。

> rt...

• 赞~ (0) nkzgm 2008-12-28 22:14:33
• 赞～ (0) lvyun 2008-12-28 22:18:58