Problem:
Koch Curve Write a program which reads an integer n and draws a Koch curve based on recursive calles of depth n . The Koch curve is well known as a kind of fractals . You can draw a Koch curve in the following algorithm:  Divide a given segment (p1, p2) into three equal segments.  Replace the middle segment by the two sides of an equilateral triangle (s, u, t) of the same length as the segment.  Repeat this procedure recursively for new segments (p1, s), (s, u), (u, t), (t, p2).    You should start (0, 0), (100, 0) as the first segment. Input An integer n is given. Output Print each point (x, y) of the Koch curve. Print a point in a line. You should start the point(0, 0), which is the endpoint of the first segment and end with the point (100, 0), the other endpoint so that you can draw the Koch curve as an unbroken line. Each solution should be given as a decimal with an arbitrary number of fractional digits, and with an absolute error of at most 10-4. Constraints  0 ≤ n ≤ 6  Sample Input 1 1 Sample Output 1 0.00000000 0.00000000
33.33333333 0.00000000
50.00000000 28.86751346
66.66666667 0.00000000
100.00000000 0.00000000 Sample Input 2 2 Sample Output 2 0.00000000 0.00000000
11.11111111 0.00000000
16.66666667 9.62250449
22.22222222 0.00000000
33.33333333 0.00000000
38.88888889 9.62250449
33.33333333 19.24500897
44.44444444 19.24500897
50.00000000 28.86751346
55.55555556 19.24500897
66.66666667 19.24500897
61.11111111 9.62250449
66.66666667 0.00000000
77.77777778 0.00000000
83.33333333 9.62250449
88.88888889 0.00000000
100.00000000 0.00000000 Notes

Solution (Python):
import math

def main():
    n = input()

    p1 = [0., 0.]
    p2 = [100., 0.]
    a = [p1,p2]
    a = rec(a,n)

    for item in a:
        print item[0], item[1]
    
def rec(a,n):
    if n == 0:
        return a
    else:
        n -= 1
        b = []
        for i in range(len(a)-1):
            p1 = a[i]
            p2 = a[i+1]
            b += koch(p1,p2)
        b.append(a[-1])
        return rec(b,n)

def koch(p1,p2):
    s  = [p1[0]+(p2[0]-p1[0])/3.,    p1[1]+(p2[1]-p1[1])/3.]
    t  = [p1[0]+2.*(p2[0]-p1[0])/3., p1[1]+2.*(p2[1]-p1[1])/3.]
    st = [t[0]-s[0],t[1]-s[1]]
    u  = [s[0]+(st[0]-math.sqrt(3)*st[1])/2., s[1]+(math.sqrt(3)*st[0]+st[1])/2.]
    return [p1,s,u,t]
    
if __name__ == "__main__":
    main()

Solution (Python):
import math


def koch(d, p1, p2):
    if d == 0:
        return

    s, t, u = [0, 0], [0, 0], [0, 0]
    s[0] = (2 * p1[0] + 1 * p2[0]) / 3
    s[1] = (2 * p1[1] + 1 * p2[1]) / 3
    t[0] = (1 * p1[0] + 2 * p2[0]) / 3
    t[1] = (1 * p1[1] + 2 * p2[1]) / 3
    u[0] = (t[0] - s[0]) * math.cos(th) - (t[1] - s[1]) * math.sin(th) + s[0]
    u[1] = (t[0] - s[0]) * math.sin(th) + (t[1] - s[1]) * math.cos(th) + s[1]

    koch(d-1, p1, s)
    print(" ".join(map(str, s)))
    koch(d-1, s, u)
    print(" ".join(map(str, u)))
    koch(d-1, u, t)
    print(" ".join(map(str, t)))
    koch(d-1, t, p2)

if __name__ == "__main__":
    th = math.radians(60)
    n = int(input())
    a = [0, 0]
    b = [100, 0]

    print(" ".join(map(str, a)))
    koch(n, a, b)
    print(" ".join(map(str, b)))

Solution (Python):
def koch_divide(p,q):
    v = [q[0]-p[0], q[1]-p[1]]
    s = [p[0]+v[0]/3, p[1]+v[1]/3]
    t = [q[0]-v[0]/3, q[1]-v[1]/3]
    u = [p[0]+v[0]*0.5-v[1]*0.288675, p[1]+v[0]*0.288675+v[1]*0.5]
    return [s,u,t,q]

def koch_curve(previous):
    vertices = [previous[0]]
    for p,q in zip(previous[:-1], previous[1:]):
        vertices.extend(koch_divide(p,q))
    return vertices

if __name__=='__main__':
    p_q = [[0.0, 0.0], [100.0, 0.0]]
    n = int(input())
    for _ in range(n):
        p_q = koch_curve(p_q)
    for vertex in p_q:
        print(" ".join(['{:.8f}'.format(x) for x in vertex]))

Solution (Python):
import math
th = math.pi/3

def koch(p2, n, points):
	p1 = points[-1]
	x, y = p2[0]-p1[0], p2[1]-p1[1]
	s = [p1[0]+x/3, p1[1]+y/3]
	t = [p1[0]+x*2/3, p1[1]+y*2/3]
	s0t = [t[0]-s[0], t[1]-s[1]]
	s0u = [math.cos(th)*s0t[0] - math.sin(th)*s0t[1],
	       math.sin(th)*s0t[0] + math.cos(th)*s0t[1]]
	u = [s[0]+s0u[0], s[1]+s0u[1]]
	
	if n == 0:
		points.append(p2)
	else:
		koch(s, n-1, points)
		koch(u, n-1, points)
		koch(t, n-1, points)
		koch(p2, n-1, points)


if __name__ == '__main__':
	n = int(input())
	p1 = [0.0, 0.0]
	p2 = [100.0, 0.0]
	points = [p1]
	koch(p2, n, points)
	[print(*p) for p in points]

Solution (Python):


"""
???????????????
??´??° n ?????\???????????±??? n ????????°????????????????????£??????????????????
?????????????????????????????§?¨????????????????????????°????????????????????????????????????

????????????????????????????????????????¨???¨????????\?????????????????????
?????????????????¨????????°???????§??????????????????¢????????¨??§???
??\????????????????????°????????¢??°????????????????????¨???????????????????????¨?????§????????????

????????????????????? (p1,p2) ??? 3 ???????????????
????????? 3???????????? 2 ??? s,ts,t ???????????¨????????£????§???¢ (s,u,t) ??????????????????
?????? (p1,s)????????? (s,u)????????? (u,t)????????? (t,p2)?????????????????°???????????????????????°????????????

"""
import math

X = 0
Y = 1
sin60 = math.sin(math.radians(60))
cos60 = math.cos(math.radians(60))

def fn(P1, P2, n, l):
    l += 1
    if l > n:
        return [P1,P2]
    
    x3 = (P2[X] -P1[X]) / 3
    y3 = (P2[Y] -P1[Y]) / 3
    xa = x3 + P1[X]
    ya = y3 + P1[Y]
    xc = P2[X] - x3
    yc = P2[Y] - y3
    xb = (xc - xa) * cos60 - (yc - ya) * sin60 + xa
    yb = (xc - xa) * sin60 + (yc - ya) * cos60 + ya
    Pa = [xa,ya]
    Pb = [xb,yb]
    Pc = [xc,yc]
    Ps = [P1]
    f1 = fn(P1,Pa,n,l)
    f2 = fn(Pa,Pb,n,l)
    f3 = fn(Pb,Pc,n,l)
    f4 = fn(Pc,P2,n,l)
    Ps.extend(f1[1:])
    Ps.extend(f2[1:])
    Ps.extend(f3[1:])
    Ps.extend(f4[1:])
    return Ps

def main():
    """ ????????? """
    num = int(input().strip())
    p1 = [0,0]
    p2 = [100,0]
    k = fn(p1,p2,num,0)
    for i in k:
        print("{} {}".format(i[0],i[1]))

if __name__ == '__main__':
    main()

Solution (Python):
from math import sqrt
q3 = sqrt(3)
fmt = "%.8f %.8f"
def koch(x0, y0, x1, y1, c):
    if c == n:
        return (fmt % (x0, y0),)
    xp = (x0*2 + x1) / 3
    yp = (y0*2 + y1) / 3

    xq = (x0 + x1*2) / 3
    yq = (y0 + y1*2) / 3

    dx = (x1 - x0) / 6
    dy = (y1 - y0) / 6

    xr = xp + (dx - dy * q3)
    yr = yp + (dx * q3 + dy)

    return koch(x0, y0, xp, yp, c+1) + koch(xp, yp, xr, yr, c+1) + koch(xr, yr, xq, yq, c+1) + koch(xq, yq, x1, y1, c+1)
n = int(input())
print(*koch(0, 0, 100, 0, 0)+(fmt % (100, 0),), sep='\n')

Solution (Python):
from math import cos,sin, pi
n = int(input())
def  koch(n, l, r):
    if n == 0:
        return
    s = ((2*l[0] + r[0])/3, (2*l[1] + r[1])/3)
    t = ((l[0] + 2*r[0])/3, (l[1] + 2*r[1])/3)
    u = ((t[0] - s[0]) * cos(pi/3) - (t[1] - s[1]) * sin(pi/3) + s[0], 
         (t[0] - s[0]) * sin(pi/3) + (t[1] - s[1]) * cos(pi/3) + s[1])
    koch(n - 1, l, s)
    print(s[0], s[1])
    koch(n - 1, s, u)
    print(u[0], u[1])
    koch(n - 1, u, t)
    print(t[0], t[1])
    koch(n - 1, t, r)

print(0, 0)
koch(n, (0, 0), (100, 0))
print(100, 0)

Solution (Python):
import math

n = int(raw_input())

class Coord():
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def show(self):
        print self.x, self.y

def calcCoord(N, start, end):
    if N == 0:
        return [start]
    s = Coord((start.x * 2.0 + end.x) /3, (start.y * 2.0 + end.y) /3)
    t = Coord((start.x + end.x * 2.0) /3, (start.y + end.y * 2.0) /3)
    u = Coord(((t.x-s.x) - (t.y-s.y) * math.sqrt(3)) /2 + s.x, ((t.x-s.x) * math.sqrt(3) + (t.y-s.y)) /2 + s.y)
    if N == 1:
        return [start, s, u, t]
    return calcCoord(N-1, start, s) + calcCoord(N-1, s, u) + calcCoord(N-1, u, t) + calcCoord(N-1, t, end)
    
start = Coord(0.0, 0.0)
end = Coord(100.0, 0.0)
ans = calcCoord(n, start, end) + [end]
for i in range(len(ans)):
    print ans[i].x, ans[i].y

Solution (Python):
import math 

def koch(n, p1, p2):
    if n==0:
        return
    
    s=((2*p1[0]+1*p2[0])/3 , (2*p1[1]+1*p2[1])/3)
   
    t=((1*p1[0]+2*p2[0])/3, (1*p1[1]+2*p2[1])/3)
    
    u= ( (t[0]-s[0])*math.cos(math.radians(60))-(t[1]-s[1])*math.sin(math.radians(60))+s[0],
        (t[0]-s[0])*math.sin(math.radians(60))+(t[1]-s[1])*math.cos(math.radians(60))+s[1])
    
    koch(n-1, p1, s)
    print(" {0:.8f} {1:.8f}".format(*s))
    koch(n-1, s , u)
    print("{0:.8f} {1:.8f}".format(*u))
    koch(n-1, u ,t)
    print("{0:.8f} {1:.8f}".format(*t))
    koch(n-1, t , p2)

p1=(0,0)
p2=(100,0)
n=int(input())

print("{0:.8f} {1:.8f}".format(*p1))
koch(n, p1, p2)
print("{0:.8f} {1:.8f}".format(*p2))

Solution (Python):
import math as mt

def kock(n, p1, p2):
    if n == 0:
        return
    s =[(2 * p1[0] + p2[0]) / 3 , (2 * p1[1] + p2[1]) / 3]
    t = [(p1[0] + 2 * p2[0]) / 3, (p1[1] + 2 * p2[1]) / 3]
    u = [(t[0]-s[0])*mt.cos(mt.radians(60))
        -(t[1]-s[1])*mt.sin(mt.radians(60)) + s[0],
         (t[0]-s[0])*mt.sin(mt.radians(60))
         +(t[1]-s[1])*mt.cos(mt.radians(60)) + s[1]]

    kock(n-1, p1, s)
    print("{0:.8f} {1:.8f}".format(s[0],s[1]))
    kock(n-1, s, u)
    print("{0:.8f} {1:.8f}".format(u[0],u[1]))
    kock(n-1, u, t)
    print("{0:.8f} {1:.8f}".format(t[0],t[1]))
    kock(n-1, t, p2)


if __name__ == '__main__':
    n = int(input())
    p1 = (0,0)
    p2 = (100,0)
    print("{0:.8f} {1:.8f}".format(p1[0],p1[1]))
    kock(n, p1, p2)
    print("{0:.8f} {1:.8f}".format(p2[0],p2[1]))

Solution (Python):
n = int(input())
r3 = 3 ** 0.5
A = (0.0, 0.0)
B = (100.0, 0.0)

def koch(n, A, B):
    if n == 0:
        return

    C1 = ((2 * A[0] + B[0]) / 3, (2 * A[1] + B[1]) / 3)
    C3 = ((A[0] + 2 * B[0]) / 3, (A[1] + 2 * B[1]) / 3)
    X, Y = C3[0] - C1[0], C3[1] - C1[1]
    C2 = (C1[0] + (X - Y * r3) / 2, C1[1] + (X * r3 + Y) / 2)

    koch(n - 1, A, C1)
    print("{:.5f} {:.5f}".format(C1[0], C1[1]))
    koch(n - 1, C1, C2)
    print("{:.5f} {:.5f}".format(C2[0], C2[1]))
    koch(n - 1, C2, C3)
    print("{:.5f} {:.5f}".format(C3[0], C3[1]))
    koch(n - 1, C3, B)

print("{:.5f} {:.5f}".format(A[0], A[1]))
koch(n, A, B)
print("{:.5f} {:.5f}".format(B[0], B[1]))

Solution (Python):


import math
r=math.radians(60)
cos_60=math.cos(r)
sin_60=math.sin(r)

n=int(input())
start_point=(0.00000000,0.00000000)
end_point=(100.00000000,0.00000000)

def koch_curve(num,p1,p2):
    if num==0:
        return 
    sx=(2*p1[0]+p2[0])/3
    sy=(2*p1[1]+p2[1])/3
    
    tx=(p1[0]+2*p2[0])/3
    ty=(p1[1]+2*p2[1])/3
    
    ux=(tx-sx)*cos_60 - (ty-sy)*sin_60 + sx
    uy=(tx-sx)*sin_60 + (ty-sy)*cos_60 + sy
    
    
    koch_curve(num-1, p1, (sx,sy))
    print("{:.8f} {:.8f}".format(sx,sy))
    koch_curve(num-1, (sx,sy), (ux,uy))
    print("{:.8f} {:.8f}".format(ux,uy))
    koch_curve(num-1, (ux,uy), (tx,ty))
    print("{:.8f} {:.8f}".format(tx,ty))
    koch_curve(num-1, (tx,ty), p2)
  

print(*start_point)
koch_curve(n, start_point, end_point)
print(*end_point)

Solution (Python):
import math

pi = math.pi

n = int(input())
p1 = [0,0]
p2 = [100,0]

def koch(n, p1, p2):
    if n == 0:
        return
    s = [(2*p1[0]+p2[0])/3.0,(2*p1[1]+p2[1])/3.0]
    t = [(1*p1[0]+2*p2[0])/3.0,(p1[1]+2*p2[1])/3.0]
    u = [(t[0]-s[0])*math.cos(pi/3) - (t[1]-s[1])*math.sin(pi/3) + s[0], 
         (t[0]-s[0])*math.sin(pi/3) + (t[1]-s[1])*math.cos(pi/3) + s[1]]
         

    koch(n - 1, p1, s)
    print(*s)
    koch(n - 1, s, u)
    print(*u)
    koch(n - 1, u, t)
    print(*t)
    koch(n - 1, t, p2)

print(*p1)
koch(n, p1, p2)
print(*p2)

Solution (Python):

import math


def koch(n, p1, p2):
    if n == 0:
        return

    sx = (2 * p1[0] + 1 * p2[0]) / 3
    sy = (2 * p1[1] + 1 * p2[1]) / 3
    s = (sx, sy)

    tx = (1 * p1[0] + 2 * p2[0]) / 3
    ty = (1 * p1[1] + 2 * p2[1]) / 3
    t = (tx, ty)

    rad60 = math.radians(60)
    ux = (tx - sx) * math.cos(rad60) - (ty - sy) * math.sin(rad60) + sx
    uy = (tx - sx) * math.sin(rad60) + (ty - sy) * math.cos(rad60) + sy
    u = (ux, uy)

    koch(n - 1, p1, s)
    print(s[0], s[1])

    koch(n - 1, s, u)
    print(u[0], u[1])

    koch(n - 1, u, t)
    print(t[0], t[1])

    koch(n - 1, t, p2)


if __name__ == "__main__":
    n = int(input())
    p1 = (0.0, 0.0)
    p2 = (100.0, 0.0)
    print(p1[0], p1[1])
    koch(n, p1, p2)
    print(p2[0], p2[1])

Solution (Python):
import math

def koch(n, a, b):
    if n == 0: return

    s, t, u = [0, 0], [0, 0], [0, 0];
    th = math.pi * 60.0 / 180.0;

    s[0] = (2.0 * a[0] + 1.0 * b[0]) / 3.0
    s[1] = (2.0 * a[1] + 1.0 * b[1]) / 3.0
    t[0] = (1.0 * a[0] + 2.0 * b[0]) / 3.0
    t[1] = (1.0 * a[1] + 2.0 * b[1]) / 3.0
    u[0] = (t[0] - s[0]) * math.cos(th) - (t[1] - s[1]) * math.sin(th) + s[0]
    u[1] = (t[0] - s[0]) * math.sin(th) + (t[1] - s[1]) * math.cos(th) + s[1]

    koch(n - 1, a, s)
    print "%.8f %.8f" % (s[0], s[1])

    koch(n - 1, s, u);
    print "%.8f %.8f" % (u[0], u[1])

    koch(n - 1, u, t)
    print "%.8f %.8f" % (t[0], t[1])

    koch(n - 1, t, b);

def main():
    a, b = [0, 0], [0, 0]

    n = int(raw_input())

    a[0], a[1] = 0, 0
    b[0], b[1] = 100, 0;

    print "%.8f %.8f" % (a[0], a[1])
    koch(n, a, b);
    print "%.8f %.8f" % (b[0], b[1])

main()

Solution (Python):
import math

def kochCurve(n,p1x,p1y,p2x,p2y):
	if n == 0:
		return
	
	qx = 2*p1x/3 + p2x/3
	qy = 2*p1y/3 + p2y/3

	rx = 2*p2x/3 + p1x/3
	ry = 2*p2y/3 + p1y/3

	s1x = rx-qx
	s1y = ry-qy

	s2x = s1x*math.cos(math.pi/3)-s1y*math.sin(math.pi/3)
	s2y = s1x*math.sin(math.pi/3)+s1y*math.cos(math.pi/3)

	s3x = s2x+qx
	s3y = s2y+qy

	kochCurve(n-1,p1x,p1y,qx,qy)
	print(qx,qy)
	kochCurve(n-1,qx,qy,s3x,s3y)
	print(s3x,s3y)
	kochCurve(n-1,s3x,s3y,rx,ry)
	print(rx,ry)
	kochCurve(n-1,rx,ry,p2x,p2y)

if __name__ == '__main__':
	n = (int)(input())
	print(0,0)
	kochCurve(n,0,0,100,0)
	print(100,0)

Solution (Python):


import math

n = int(raw_input())

def vector_rot(vector, radian):
	new_x = vector[0] * math.cos(radian) - vector[1] * math.sin(radian)
	new_y = vector[0] * math.sin(radian) + vector[1] * math.cos(radian)
	return [new_x, new_y]

def vector_add(v1, v2):
	new_v = []
	for i in range(2):
		add = v1[i] + v2[i]
		new_v.append(add)
	return new_v

def makepoint(p_A1, p_A2):
	x_p_C1 = (p_A2[0] - p_A1[0]) / 3 + p_A1[0]
	y_p_C1 = (p_A2[1] - p_A1[1]) / 3 + p_A1[1]
	x_p_C3 = (p_A2[0] - p_A1[0]) * 2 / 3 + p_A1[0]
	y_p_C3 = (p_A2[1] - p_A1[1]) * 2 / 3 + p_A1[1]

	p_C1 = [x_p_C1, y_p_C1]
	p_C3 = [x_p_C3, y_p_C3]

	v01 = [x_p_C1 - p_A1[0], y_p_C1 - p_A1[1]]
	rot_v01 = vector_rot(v01, 60 * math.pi / 180)
	v02 = vector_add(v01, rot_v01)
	p_C2 = vector_add(p_A1, v02)	
	
	C = [p_C1, p_C2, p_C3]
	return C

A = [[0., 0.],[100., 0.]]
for i in range(n):
	B = []
	for j in range(len(A)-1): 
		C = makepoint(A[j], A[j+1]) 
		B.append(A[j])
		for p in C:
			B.append(p)
		
	B.append(A[-1]) 
	A = B

for x in A:
	print("{:.8f}".format(x[0])),
	print("{:.8f}".format(x[1]))

Solution (Python):


import math

def kock(n,p1x,p1y,p2x,p2y):
    if n==0:
        pass
    else:
        sx=(2*p1x+p2x)/3
        sy=(2*p1y+p2y)/3
        tx=(p1x+2*p2x)/3
        ty=(p1y+2*p2y)/3

        ux=(tx-sx)*math.cos(math.pi*1/3)-(ty-sy)*math.sin(math.pi*1/3)+sx
        uy=(tx-sx)*math.sin(math.pi*1/3)+(ty-sy)*math.cos(math.pi*1/3)+sy

        kock(n-1,p1x,p1y,sx,sy)
        print(sx,sy)
        kock(n - 1, sx, sy, ux, uy)
        print(ux,uy)
        kock(n - 1, ux, uy, tx, ty)
        print(tx,ty)
        kock(n - 1, tx, ty, p2x, p2y)

n=int(input().strip())

zero=0.0
hundred=100.0
print(zero,zero)
kock(n,0,0,100,0)
print(hundred,zero)

Solution (Python):

import math


def cut_into_three(start: list, end: list) -> list:
    x1 = (2*start[0]+end[0])/3
    y1 = (2*start[1]+end[1])/3
    mid_point1 = [x1, y1]

    x2 = (start[0]+2*end[0])/3
    y2 = (start[1]+2*end[1])/3
    mid_point2 = [x2, y2]

    points_list = [start, mid_point1, mid_point2, end]
    return points_list


def equil_triangle(point1: list, point2: list) -> list:
    cos60 = math.cos(math.pi / 3)
    sin60 = math.sin(math.pi / 3)

    x = (point2[0] - point1[0])*cos60 - (point2[1]-point1[1])*sin60 + point1[0]
    y = (point2[0] - point1[0])*sin60 + (point2[1]-point1[1])*cos60 + point1[1]

    return [x, y]


def make_projection(start: list, end: list) -> list:
    points_list = cut_into_three(start, end)
    projection_point = equil_triangle(points_list[1], points_list[2])
    points_list.insert(2, projection_point)
    return points_list


def koch_curve(start: list, end: list, number: int) -> list:
    if number == 0:
        return [start, end]
    else:
        points_list = make_projection(start, end)
        list1 = koch_curve(points_list[0], points_list[1], number-1)
        list2 = koch_curve(points_list[1], points_list[2], number-1)
        list3 = koch_curve(points_list[2], points_list[3], number-1)
        list4 = koch_curve(points_list[3], points_list[4], number-1)
        new_points_list = list1 + list2[1:] + list3[1:] + list4[1:]
        return new_points_list


if __name__ == '__main__':
    n = int(input())
    p1 = [0, 0]
    p2 = [100, 0]
    fractal_points = koch_curve(p1, p2, n)
    for i in fractal_points:
        print(' '.join(map(str, i)))

Solution (Python):
import math


def koch(n, p1x, p1y, p2x, p2y):
    if n == 0:
        return

    sx = (2*p1x + 1*p2x)/3
    sy = (2*p1y + 1*p2y)/3
    tx = (1*p1x + 2*p2x)/3
    ty = (1*p1y + 2*p2y)/3
    theta = math.pi/3
    ux = math.cos(theta)*(tx-sx) - math.sin(theta)*(ty-sy) + sx
    uy = math.sin(theta)*(tx-sx) + math.cos(theta)*(ty-sy) + sy

    koch(n-1, p1x, p1y, sx, sy)
    print("{:.5f} {:.5f}".format(sx, sy))
    koch(n-1, sx, sy, ux, uy)
    print("{:.5f} {:.5f}".format(ux, uy))
    koch(n-1, ux, uy, tx, ty)
    print("{:.5f} {:.5f}".format(tx, ty))
    koch(n-1, tx, ty, p2x, p2y)

n = int(input())

p1x, p1y = 0.0, 0.0
p2x, p2y = 100.0, 0.0

print("{:.5f} {:.5f}".format(p1x, p1y))
koch(n, p1x, p1y, p2x, p2y)
print("{:.5f} {:.5f}".format(p2x, p2y))

Solution (Python):
from math import *
def koch(n, a, b):
    if n == 0:
        return
    th = pi * 60.0 / 180.0
    s = complex((2.0 * a.real + 1.0 * b.real) / 3.0, (2.0 * a.imag + 1.0 * b.imag) / 3.0)
    t = complex((1.0 * a.real + 2.0 * b.real) / 3.0, (1.0 * a.imag + 2.0 * b.imag) / 3.0)
    u = complex((t.real - s.real) * cos(th) - (t.imag - s.imag) * sin(th) + s.real,
                (t.real - s.real) * sin(th) + (t.imag - s.imag) * cos(th) + s.imag)
    koch(n - 1, a, s)
    print(s.real, s.imag)
    koch(n - 1, s, u)
    print(u.real, u.imag)
    koch(n - 1, u, t)
    print(t.real, t.imag)
    koch(n - 1, t, b)
n = int(input())
a = complex(0, 0)
b = complex(100, 0)
print(a.real, a.imag)
koch(n, a, b)
print(b.real, b.imag)

Solution (Python):
from math import *
c60 = cos(radians(60))
s60 = sin(radians(60))
def koch(d, p1, p2):
    if d == 0:
        return
    sx = (2 * p1[0] + p2[0]) / 3
    sy = (2 * p1[1] + p2[1]) / 3
    tx = (p1[0] + 2 * p2[0]) / 3
    ty = (p1[1] + 2 * p2[1]) / 3
    ux = (tx - sx) * c60 - (ty - sy) * s60 + sx
    uy = (tx - sx) * s60 + (ty - sy) * c60 + sy
    koch(d - 1, p1, (sx, sy))
    print("{0:.8f} {1:.8f}".format(sx, sy))
    koch(d - 1, (sx, sy), (ux, uy))
    print("{0:.8f} {1:.8f}".format(ux, uy))
    koch(d - 1, (ux, uy), (tx, ty))
    print("{0:.8f} {1:.8f}".format(tx, ty))
    koch(d - 1, (tx, ty), p2)
n = int(input())
ax, ay = 0, 0
bx, by = 100, 0
print("{0:.8f} {1:.8f}".format(ax, ay))
koch(n, (ax, ay), (bx, by))
print("{0:.8f} {1:.8f}".format(bx, by))

Solution (Python):

from math import sin, cos, pi



def koch(d, p1, p2):
    if d == 0:
        return

    s = [None, None]
    u = [None, None]
    t = [None, None]
    
    s[0] = (2*p1[0] + p2[0])/3
    s[1] = (2*p1[1] + p2[1])/3
    t[0] = (p1[0] + 2*p2[0])/3
    t[1] = (p1[1] + 2*p2[1])/3
    u[0] = (t[0] - s[0])*cos(1/3*pi) - (t[1] - s[1])*sin(1/3*pi) + s[0]
    u[1] = (t[0] - s[0])*sin(1/3*pi) + (t[1] - s[1])*cos(1/3*pi) + s[1]

    koch(d-1, p1, s)
    print(s[0], s[1])
    koch(d-1, s, u)
    print(u[0], u[1])
    koch(d-1, u, t)
    print(t[0], t[1])
    koch(d-1, t, p2)

if __name__ == '__main__':

    n = int(input())
    a = [0, 0]
    b = [100, 0]

    print(a[0], a[1])
    koch(n ,a ,b)
    print(b[0] ,b[1])

Solution (Python):
import math

class point:

    def __init__(self, p):
        self._x = p[0]
        self._y = p[1]

    def disp(self):
        print("{0:f} {1:f}".format(self._x, self._y))

    @property
    def x(self):
        return self._x

    @property
    def y(self):
        return self._y


def get_s(p1, p2):
    p = point((p1.x/3*2 + p2.x/3, p1.y/3*2 + p2.y/3))
    return p


def get_t(p1, p2):
    p = point((p1.x/3 + p2.x/3*2, p1.y/3 + p2.y/3*2))
    return p


def get_u(s, t):
    x = (t.x - s.x)*math.cos(math.radians(60)) - (t.y - s.y)*math.sin(math.radians(60)) + s.x
    y = (t.x - s.x)*math.sin(math.radians(60)) + (t.y - s.y)*math.cos(math.radians(60)) + s.y
    return point((x, y))


def kock(n, p1, p2):
    if n == 0:
        return
    else:
        s = get_s(p1, p2)
        t = get_t(p1, p2)
        u = get_u(s, t)

        kock(n-1, p1, s)
        s.disp()
        kock(n-1, s, u)
        u.disp()
        kock(n-1, u, t)
        t.disp()
        kock(n-1, t, p2)

        return


if __name__ == '__main__':

    n = int(input())

    p1 = point((0, 0))
    p2 = point((100, 0))

    p1.disp()
    kock(n, p1, p2)
    p2.disp()

Solution (Python):
import math
dig_six = math.radians(60)

def koch(d, p1, p2):
    if d == 0:
        return d
    
    s_x = (2*p1[0]+1 * p2[0]) / 3
    s_y = (2*p1[1]+1 * p2[1]) / 3
    s = (s_x, s_y)
    t_x = (1*p1[0]+2 * p2[0]) / 3
    t_y = (1*p1[1]+2 * p2[1]) / 3
    t = (t_x, t_y)
    u_x = (t_x - s_x)*math.cos(dig_six) - (t_y - s_y)*math.sin(dig_six) + s_x
    u_y = (t_x - s_x)*math.sin(dig_six) + (t_y - s_y)*math.cos(dig_six) + s_y
    u = (u_x, u_y)
    
    koch(d-1, p1, s)
    print (' '.join([str(x) for x in s]))
    koch(d-1, s, u)
    print (' '.join([str(x) for x in u]))
    koch(d-1, u, t)
    print (' '.join([str(x) for x in t]))
    koch(d-1, t, p2)

if __name__ == '__main__':
    iterate = int(input())
    p1 = (0.0, 0.0)
    p2 = (100.0, 0.0)
    print (' '.join([str(x) for x in p1]))
    koch(iterate, p1, p2)
    print (' '.join([str(x) for x in p2]))

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  s=a+(b-a)/3;u,t=s+(s-a)*(1+3**.5*1j)/2,b-(b-a)/3
  p+=[a,s,u,t]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  s=a+(b-a)/3;u,t=s+(s-a)*(1+3**.5*1j)/2,b-(b-a)/3
  p+=[a,s,u,t]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3;u,t=r+a+r*(1+3**.5*1j)/2,b-r
  p+=[a,r+a,u,t]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,(a+b)/2+r*1j*3**.5/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,(a+b)/2+r*1j*3**.5/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
import cmath
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*cmath.rect(1,cmath.pi/3),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
import cmath
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*cmath.rect(1,cmath.pi/3),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
import cmath
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*cmath.rect(1,cmath.pi/3),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
import cmath
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*cmath.rect(1,cmath.pi/3),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
import cmath
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
import cmath
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
import cmath
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(1+3**.5*1j)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,a+r+r*(.5+3**.5*.5j),b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,(a+b+r*1j*3**.5)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,(a+b+r*1j*3**.5)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,(a+b+r*1j*3**.5)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,(a+b+r*1j*3**.5)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,(a+b+r*1j*3**.5)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a,a+r,(a+b+r*1j*3**.5)/2,b-r]
 d=p+[d[-1]]
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[d[0]]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a+r,a+r+r*(1+3**.5*1j)/2,b-r,b]
 d=p
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[d[0]]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a+r,a+r+r*(1+3**.5*1j)/2,b-r,b]
 d=p
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[d[0]]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a+r,a+r+r*(1+3**.5*1j)/2,b-r,b]
 d=p
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[d[0]]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a+r,a+r+r*(1+3**.5*1j)/2,b-r,b]
 d=p
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[d[0]]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a+r,a+r+r*(1+3**.5*1j)/2,b-r,b]
 d=p
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
def f():
 global d
 p=[d[0]]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a+r,a+r+r*(1+3**.5*1j)/2,b-r,b]
 d=p
d=[0j,100+0j]
for _ in[0]*int(input()):f()
for e in d:print(e.real,e.imag)

Solution (Python):
d=[0j,100+0j]
for _ in[0]*int(input()):
 p=[d[0]]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a+r,a+r+r*(1+3**.5*1j)/2,b-r,b]
 d=p
for e in d:print(e.real,e.imag)

Solution (Python):
d=[0j,100+0j]
for _ in[0]*int(input()):
 p=[d[0]]
 for i in range(len(d)-1):
  a,b=d[i],d[i+1]
  r=(b-a)/3
  p+=[a+r,a+r+r*(1+3**.5*1j)/2,b-r,b]
 d=p
for e in d:print(e.real,e.imag)