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