C - Koch Curve

cpaojalds1

最終更新日

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_C (新しいタブで開く)

問題文

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

コッホ曲線?

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

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

制約

サンプル

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; }