C - Koch Curve

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_C

問題文

深さ $n$ の再起呼び出しによって作成されるコッホ曲線の頂点の座標を出力してね。

コッホ曲線？

• 与えられた線分 $(p_1, p_2)$ を 3 等分
• 3 等分する 2 点 $s, t$ を頂点とする正三角形 $(s, u, t)$ を作成
• 線分 $(p_1, s), (s, u), (u, t), (t, p_2)$ を再帰的に

$(0, 0), (100, 0)$ を端点としたとき、深さ $n$ のコッホ曲線の頂点の座標は？
絶対誤差 $10^{-4}$ 以下なら許容。

制約

• $0 \le n \le 6$

サンプル

I/O 1

1

0.00000000 0.00000000
33.33333333 0.00000000
50.00000000 28.86751346
66.66666667 0.00000000
100.00000000 0.00000000

I/O 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

考察

いわれた再帰をやるだけ

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_5_C/judge/6771428/C++17

typedef complex<double> P;
vector<P> ans;

void koch(const P p1, const P p2, const int dep) {
  if (dep <= 0) return;
  P s = p1 + (p2 - p1) / 3.0;
  P t = p2 - (p2 - p1) / 3.0;
  P u = s + (t - s) * P(0.5, sqrt(3.0) / 2.0);
  koch(p1, s, dep - 1);
  ans.push_back(s);
  koch(s, u, dep - 1);
  ans.push_back(u);
  koch(u, t, dep - 1);
  ans.push_back(t);
  koch(t, p2, dep - 1);
}

int main() {
  int n;
  cin >> n;
  P p1(0, 0), p2(100, 0);
  ans.push_back(p1);
  koch(p1, p2, n);
  ans.push_back(p2);
  cout << fixed << setprecision(10);
  rep(i, ans.size()) {
    cout << ans[i].real() << " " << ans[i].imag() << endl;
  }
  return 0;
}