题目地址:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_C
Koch
前言
只针对如何实现这个算法, 算法具体的描述请看原文
分析
s 与 t 分别是两个三等分点, 所以可以很容易的通过p1与p2求出来
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;
关于 u 的求解, 在n = 1的那张图里, 很容易看到 u 的x坐标与中点坐标相同, u 的y坐标在中点坐标之上.
设 s 与 t 之间的距离为 l, u与线段 s t 之间的距离为h.如下图所示
koch1
于是可以知道
u.x = mid.x; u.y = mid.y + h;
而通过观察n=3的那张图, 发现p1(起始点)与p2(结束点)总共有六种不同的状态
koch2
取其中一种状态进行分析
koch3
在位置关系为斜向右上方时, u 的x等于中点的 x - h * cos30, u 的y等于中点的 y + h * sin30 , 其他的几种关系也可以分析出来, 最后的关于u的计算代码如下:
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);
}
