コッホ曲線
整数 $n$ を入力し、深さ $n$ の再帰呼び出しによって作成されるコッホ曲線の頂点の座標を出力するプログラムを作成してください。
コッホ曲線はフラクタルの一種として知られています。フラクタルとは再帰的な構造を持つ図形のことで、以下のように再帰的な関数の呼び出しを用いて描画することができます。
- 与えられた線分 $(p1, p2)$ を 3 等分する。
- 線分を 3等分する 2 点 $s, t$ を頂点とする正三角形 $(s, u, t)$ を作成する。
- 線分 $(p1, s)$、線分 $(s, u)$、線分 $(u, t)$、線分 $(t, p2)$に対して再帰的に同じ操作を繰り返す。
$(0, 0), (100, 0)$ を端点とします。
入力
1 つの整数 $n$ が与えられます。
出力
コッホ曲線の各頂点の座標 $(x, y)$ を出力してください。１行に１点の座標を出力してください。端点の１つ $(0, 0)$ から開始し、一方の端点 $(100, 0)$ で終えるひと続きの線分の列となる順番に出力してください。出力は 0.0001 以下の誤差を含んでいてもよいものとします。
制約
- $ 0 \leq n \leq 6$
入力例 1
1
出力例 1
0.00000000 0.00000000 33.33333333 0.00000000 50.00000000 28.86751346 66.66666667 0.00000000 100.00000000 0.00000000
入力例 2
2
出力例 2
0.00000000 0.00000000 11.11111111 0.00000000 16.66666667 9.62250449 22.22222222 0.00000000 33.33333333 0.00000000 38.88888889 9.62250449 33.33333333 19.24500897 44.44444444 19.24500897 50.00000000 28.86751346 55.55555556 19.24500897 66.66666667 19.24500897 61.11111111 9.62250449 66.66666667 0.00000000 77.77777778 0.00000000 83.33333333 9.62250449 88.88888889 0.00000000 100.00000000 0.00000000