Koch Curve

http://acm.zju.edu.cn/show_problem.php?pid=1575

Time limit: 1 Seconds

Memory limit: 32768K

1575.jpg

Koch Curve is very common in fractal. It has infinite length. The figure above illustrates the creation of a Koch Curve. A line segment L1 (a->d) is given. It is cut into three equal parts. L2 is obtained by rotating the middle part counter-clockwise to vector s->d. The length satisfies the constraint p0p1 = p1p2 = p2p3 = p3p4. We further process on p0->p1, p1->p2, p2->p3, p3->p4 to obtain L3. We proceed with such iteration to obtain Koch Curve. Since the length is increased by 4/3 each iteration, the length of Koch Curve is infinite. With given s and d, you are to provide the result of the n-th iteration.

1. Input

There are multiple tests, in each test.

The first line contains an integer n (1 <= n <= 7).

The second line contains four floating numbers sx, sy, dx, dy.

2. Output

For each test print the vertex in the order from s to d. Keep two digits after decimal point.

Print a blank line after each case.

3. Sample Input

1
0 0 3 0
1
3 0 0 0

4. Sample Output

0.00 0.00
1.00 0.00
1.50 0.87
2.00 0.00
3.00 0.00

3.00 0.00
2.00 0.00
1.50 -0.87
1.00 0.00
0.00 0.00

Author: DU, Peng

Problem Source: ZOJ Monthly, April 2003


   1 /*Written by czk*/
   2 #include <iostream>
   3 #include <iomanip>
   4 using namespace std;
   5 
   6 void koch(int n, double sx, double sy, double dx, double dy, bool print) {
   7         if(n < 0) return;
   8         double x1 = (sx * 2+  dx) / 3;
   9         double y1 = (sy * 2+  dy) / 3;
  10 
  11 
  12         double x2 = ( sx + 2 * dx) / 3;
  13         double y2 = ( sy + 2 * dy) / 3;
  14 
  15         double xm = x1 + 0.5*(x2-x1) - 1.7320508075688772935274463415059/2*(y2-y1);
  16         double ym = y1 + 1.7320508075688772935274463415059/2 * (x2 - x1)  + 0.5 * (y2-y1);
  17 
  18         koch(n-1, sx, sy, x1, y1, true);
  19         koch(n-1, x1, y1, xm, ym, true);
  20         koch(n-1, xm, ym, x2, y2, true);
  21         koch(n-1, x2, y2, dx, dy, false);
  22         if(print) 
  23                 cout <<setprecision(2)<< fixed<< dx << " "<< dy << '\n';
  24 }
  25 
  26 int main() {
  27         while(1) {
  28                 int n;
  29                 double sx, sy, dx, dy;
  30                 cin >> n >> sx >> sy >> dx >> dy;
  31                 if(cin.eof()) 
  32                         break;
  33                 cout <<setprecision(2)<< fixed<< sx << " "<< sy << '\n';        
  34                 koch(n, sx, sy, dx, dy, true);
  35                 cout << endl;           
  36         }
  37 }

zju1575 (2008-02-23 15:34:15由localhost编辑)

ch3n2k.com | Copyright (c) 2004-2020 czk.