題目地址:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_C
Koch
前言
只針對(duì)如何實(shí)現(xiàn)這個(gè)算法, 算法具體的描述請(qǐng)看原文
分析
s 與 t 分別是兩個(gè)三等分點(diǎn), 所以可以很容易的通過(guò)p1與p2求出來(lái)
s.x = (double) 1 / 3 * (p2.x - p1.x) + p1.x;
s.y = (double) 1 / 3 * (p2.y - p1.y) + p1.y;
t.x = (double) 2 / 3 * (p2.x - p1.x) + p1.x;
t.y = (double) 2 / 3 * (p2.y - p1.y) + p1.y;
關(guān)于 u 的求解, 在n = 1的那張圖里, 很容易看到 u 的x坐標(biāo)與中點(diǎn)坐標(biāo)相同, u 的y坐標(biāo)在中點(diǎn)坐標(biāo)之上.
設(shè) s 與 t 之間的距離為 l, u與線段 s t 之間的距離為h.如下圖所示
koch1
于是可以知道
u.x = mid.x; u.y = mid.y + h;
而通過(guò)觀察n=3的那張圖, 發(fā)現(xiàn)p1(起始點(diǎn))與p2(結(jié)束點(diǎn))總共有六種不同的狀態(tài)
koch2
取其中一種狀態(tài)進(jìn)行分析
koch3
在位置關(guān)系為斜向右上方時(shí), u 的x等于中點(diǎn)的 x - h * cos30, u 的y等于中點(diǎn)的 y + h * sin30 , 其他的幾種關(guān)系也可以分析出來(lái), 最后的關(guān)于u的計(jì)算代碼如下:
if (p2.y - p1.y < 0.00000001 && p2.y - p1.y > -0.00000001)
{
u.x = mid.x;
if (p2.x > p1.x)
u.y = mid.y + h;
else
u.y = mid.y - h;
}
else if (p2.y > p1.y)
{
u.x = mid.x - 0.75 * l;
if (p2.x > p1.x)
u.y = mid.y + 0.5 * h;
else
u.y = mid.y - 0.5 * h;
}
else
{
u.x = mid.x + 0.75 * l;
if (p2.x > p1.x)
u.y = mid.y + 0.5 * h;
else
u.y = mid.y - 0.5 * h;
}
附上整體代碼
// ALDS1-05-C KochCurve.cpp
// Written by: by_sknight
// Date: 13/12/2018
#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
class Point
{
public:
Point(double x = 0, double y = 0) {this->x = x; this->y = y;}
double x;
double y;
void show() const {cout << x << " " << y << endl;}
};
void koch(const Point &p1, const Point &p2, int n);
int main(void)
{
cout << fixed << setprecision(8);
int n;
cin >> n;
Point p1(0, 0), p2(100, 0);
koch(p1, p2, n);
p2.show();
return 0;
}
void koch(const Point &p1, const Point &p2, int n)
{
if (n == 0)
{
p1.show();
return;
}
Point s, u, t;
s.x = (double) 1 / 3 * (p2.x - p1.x) + p1.x;
s.y = (double) 1 / 3 * (p2.y - p1.y) + p1.y;
t.x = (double) 2 / 3 * (p2.x - p1.x) + p1.x;
t.y = (double) 2 / 3 * (p2.y - p1.y) + p1.y;
double l = (double) 1 / 3 * sqrt(pow(p2.y - p1.y, 2) + pow(p2.x - p1.x, 2));
double h = (double) sqrt(3) / 2 * l;
Point mid;
mid.x = (double) 1 / 2 * (p2.x - p1.x) + p1.x;
mid.y = (double) 1 / 2 * (p2.y - p1.y) + p1.y;
if (p2.y - p1.y < 0.00000001 && p2.y - p1.y > -0.00000001)
{
u.x = mid.x;
if (p2.x > p1.x)
u.y = mid.y + h;
else
u.y = mid.y - h;
}
else if (p2.y > p1.y)
{
u.x = mid.x - 0.75 * l;
if (p2.x > p1.x)
u.y = mid.y + 0.5 * h;
else
u.y = mid.y - 0.5 * h;
}
else
{
u.x = mid.x + 0.75 * l;
if (p2.x > p1.x)
u.y = mid.y + 0.5 * h;
else
u.y = mid.y - 0.5 * h;
}
// s, u, t ok!
koch(p1, s, n - 1);
koch(s, u, n - 1);
koch(u, t, n - 1);
koch(t, p2, n - 1);
}
