Coch Curve
問題 : AOJ のALDS のDivide and Conquer の中から見れます.
解法 :
問題文で示されているように再帰を行う. 正三角形の頂点の座標$(mx, my)$ は, その左隣の点を$m1 = (lx, ly)$, 右隣を$m2 = (rx, ry)$ とし, $m2 - m1$ ベクトルを90 度回転させたものを $\dfrac{\sqrt{3}}{2}$ 倍して, $a = (\dfrac{lx + rx}{2},\ \dfrac{ly + ry}{2})$ に加えれば良い.
コード :
#include <cstdio> #include <cmath> #include <algorithm> #include <vector> using namespace std; void Coch(int n, Point l, Point r) { if (n == 0){ printf("%lf %lf\n", r.x, r.y); return; } Point m1, m2; m1 = (l * 2 + r) * (1 / 3.0); m2 = (l + r * 2) * (1 / 3.0); double len = abs(m2 - m1); Point m3 = rotate(m2 - m1, Point(0, 0), M_PI / 2); m3 = (m1 + m2) * 0.5 + unitVector(m3) * (len * sqrt(3) / 2); Coch(n - 1, l, m1); Coch(n - 1, m1, m3); Coch(n - 1, m3, m2); Coch(n - 1, m2, r); } int main() { int n; scanf("%d", &n); printf("%lf %lf\n", 0.0, 0.0); Coch(n, Point(0, 0), Point(100, 0)); }