ALDS1_5_C コッホ曲線をC++で解いてみた[AIZU ONLINE JUDGE]

AIZU ONLINE JUDGE

こんにちは! mnbd(@mnbbbbbd)です。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文

整数 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) を出力してください。1行に1点の座標を出力してください。端点の1つ (0,0) から開始し、一方の端点 (100,0) で終えるひと続きの線分の列となる順番に出力してください。出力は 0.0001 以下の誤差を含んでいてもよいものとします。

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

解答

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x;
    double y;
};

void print_point(Point a) { cout << fixed << setprecision(8) << a.x << " " << a.y << endl; }

void koch(int d, Point p, Point q) {
    if(d == 0) {
        return;
    }

    Point s, u, t;
    s.x = (2 * p.x + q.x) / 3.0;
    s.y = (2 * p.y + q.y) / 3.0;
    t.x = (p.x + 2 * q.x) / 3.0;
    t.y = (p.y + 2 * q.y) / 3.0;

    double ang = M_PI * 60 / 180.0; //度をラジアンに変換
    u.x = (t.x - s.x) * cos(ang) - (t.y - s.y) * sin(ang) + s.x;
    u.y = (t.x - s.x) * sin(ang) + (t.y - s.y) * cos(ang) + s.y;

    koch(d - 1, p, s);
    print_point(s);
    koch(d - 1, s, u);
    print_point(u);
    koch(d - 1, u, t);
    print_point(t);
    koch(d - 1, t, q);
}

int main() {
    int n;
    cin >> n;

    Point s1, s2;
    s1.x = 0;
    s1.y = 0;
    s2.x = 100;
    s2.y = 0;

    print_point(s1);
    koch(n, s1, s2);
    print_point(s2);

    return 0;
}

感想

コッホ曲線というものを知りませんでしたが、問題文に説明と一般解説にも細かい計算式が出ています。

私は、度をラジアンに変換するなどの数学的?なことを理解していなかったためにまったくわかりませんでした。

解説付きというのもあってか正答率50%台ということで、数学的知識があれば解きやすい問題だったのかもしれません。

まとめ

AIZU ONLINE JUDGEの「ALDS1_5_C コッホ曲線」を解いてみましたので、その回答と解説をご紹介いたしました。

少しずつですが、プログラミングの勉強をしています。
まだ初心者ですが、よかったらつながっていただけると嬉しいです。
Twitterアカウント(@mnbbbbbd

以上です。
読んでいただきありがとうございました!