はじめに
「Icosahedron」writerのKowerKointです。
計算幾何がどんどん居場所を失っているので復権させたく出題しました。
辛かった方もこれを機に幾何に慣れましょう。
解法1
方針
基準となる正二十面体を$1$つ決めて、そこからの回転移動・拡大縮小・平行移動の組み合わせとして答えの正二十面体を定めます。
点$(x,y,z)$を回転移動・拡大縮小・平行移動の組み合わせ(アフィン変換)によって移動した先の点$(x'',y'',z'')$は行列・ベクトルの演算として求められます。
\overrightarrow{x}=
\begin{pmatrix}
x \\
y \\
z \\
\end{pmatrix}
,
\overrightarrow{x''}=
\begin{pmatrix}
x'' \\
y'' \\
z'' \\
\end{pmatrix}
とすると、$\overrightarrow{x''}$はある行列$A$とベクトル$\overrightarrow{t}$を用いて
\overrightarrow{x''}=S\overrightarrow{x}+\overrightarrow{t}
と表されます。
$S$は回転行列の定数倍であるから特殊な制約が課されますが、ここでは気にしないこととします。
したがって、いい感じに基準の正二十面体を決めてそこからの変換を表す$S$と$\overrightarrow{t}$を求めたいことがわかります。
この変換を通したあとの座標に$''$をつけることにしているので、わかりやすくするために以後は入力される$A,B,C$を$A'',B'',C''$に書き換えて説明します。
基準座標
検索ありコンテストなんだからググっちゃいます。
すると高校数学の美しい物語様がありがたいことにいい感じの座標をまとめてくださっています。
(導出を考えてみるのも面白いです。無理な話ではありません。)
以下の合計12個の点は，1辺の長さが2の正二十面体の頂点となっている。
- 緑：$xy$ 平面上の長方形の4頂点 $(\pm 1,\pm\phi,0)$
- 青：$yz$ 平面上の長方形の4頂点 $(0,\pm 1,\pm\phi)$
- 赤：$zx$ 平面上の長方形の4頂点 $(\pm\phi,0,\pm 1)$
ただし，$\phi=\dfrac{1+\sqrt{5}}{2}$
これを基準にしていきましょう。
tを求める
$\overrightarrow{t}$を求めていきましょう。
これは平行移動を表す部分です。
平行移動を考えるときは、回転移動・拡大縮小で不変の点として図形から一意な点を決めておくといいです。
こういう場合の定石として、中心を基準にします。
注) 中心の定義をしていないのでこの考えには厳密性が足りませんが、正多面体なのでどんな定義で中心を定めても基本的に一意になることが直感的に理解できることに頼っています
基準の正二十面体での中心点は原点$O(0,0,0)$です。
$A,B,C$の座標から、移動後の正二十面体の中心点$O''$の座標を求めたいです。
いくつか方法があると思いますが、三角錐$O''-A''B''C''$に注目します。
これは正三角錐ですから、三角形$A''B''C''$の重心を$G''$とすると、$\overrightarrow{A''B''}\perp\overrightarrow{G''O''},\overrightarrow{A''C''}\perp\overrightarrow{G''O''}$が成り立ち、$k$を実数として$\overrightarrow{G''O''}=\dfrac{k}{|\overrightarrow{A''B''}|}(\overrightarrow{A''B''}\times\overrightarrow{A''C''})$と表されます。
この$k$はどの正二十面体でも一定です。
したがって、変形後の正二十面体の代わりに座標が全てわかっている基準の正二十面体で$k$を計算することができ、$k=\dfrac{1+\phi}{3}$を得ます。
以上を用いて$O''$の座標が判明しました。
$\overrightarrow{t}=\overrightarrow{OO''}$から、$O''$の座標がそのまま$\overrightarrow{t}$の成分になります。
展開図の頂点番号と基準正二十面体の頂点を対応付ける
展開図を見ながら、基準正二十面体に頂点番号($A,B,C,1,2,3,4,5,6,7,8,9$)をつけます。
これは気合で頑張ってください。
ヒント(気づき)として、この正二十面体の一辺の長さは$2$で
(0-0)^2+\{1-(-1)\}^2+(\phi-\phi)^2=2^2 \\
(1-0)^2+(\phi-1)^2+(0-\phi)^2=2^2
であり、この$2$種類の形の$2$頂点のみが隣接することを考えると簡単にハマっていくと思います。
当然コンピュータが使用できるコンテストですから、できない場合はmatplotlibなどの3D描画ツールで座標を確認しながら振っていくとできます。
一例として以下の振り方があります。
以後はこれに従います。
A(0,1,\phi) \\
B(\phi,0,1) \\
C(1,\phi,0) \\
1(-1,\phi,0) \\
2(-\phi,0,1) \\
3(0,-1,\phi) \\
4(\phi,0,-1) \\
5(0,1,-\phi) \\
6(-\phi,0,-1) \\
7(-1,-\phi,0) \\
8(1,-\phi,0) \\
9(0,-1,-\phi)
Sを求める
ここまで来たら頭の痛くなる作業はありません。あと少し頑張りましょう。
改めて座標変換の式を見ます。
x''=Sx+t
移行します。
Sx=x''-t
さて、私達はこの式を満たす$x$と$x''$の組を$3$つ知っています。
$(A,A''),(B,B''),(C,C'')$です。
$A,B,C,A'',B'',C''$を列ベクトルの形で書き表すことにし、
X=
\begin{pmatrix}
A & B & C
\end{pmatrix} \\
X'=
\begin{pmatrix}
A''-t & B''-t & C''-t
\end{pmatrix}
という$3$行$3$列の行列の形にすると、
SX=X'
が成り立ちます(列ベクトルを$3$つ並べたものに左から行列をかける場合、
結果もそれぞれの列ベクトルに左から行列をかけたものを並べた行列になります)。
この式の両辺に右から$X$の逆行列をかけることで、$S$を得られます。
お疲れ様でした。
答えを求める
あとは求めたい頂点番号の基準正二十面体での座標それぞれにに$x''=Sx+t$を適用すればいいですね。
解法2
注) この方法は想定解法ではありましたが、僕自身はACの再現をしていないため説明が間違っている可能性があります(testerによるACは確認しています)
ある三角形の頂点座標がわかっているとき、その三角形と辺を共有する三角形の残り$1$つの座標を求める方法を確立します。
ここでは例として、三角形$ABC$と辺$AC$を共有する三角形$1AC$の頂点$1$の座標を求めます。
$M$を辺$AC$の中点とし、$\theta=\angle BM1$とします。
座標がわかっている正二十面体で内積から計算したり入出力例からエスパーするなどして$\cos\theta=\dfrac{1-\phi}{3}$を得ます。
あとは
\angle BM1 = \theta \\
|BM|=|1M| \\
AC\perp 1M
などの連立方程式を解いて$1$の座標が得られます。
同じことを繰り返して全ての座標を埋めます。