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):
from math import sqrt

def koch(n, c1, c2):
    if n == 0:
        return
    
    
    v = [c2[0] - c1[0], c2[1] - c1[1]]

    s = [c1[0] + v[0] / 3, c1[1] + v[1] / 3]
    t = [c1[0] + 2 * v[0] / 3, c1[1] + 2 * v[1] / 3]
    u = [c1[0] + v[0]/2 - v[1] * sqrt(3) / 6, c1[1] + v[1]/2 + v[0] * sqrt(3) / 6]

    koch(n-1, c1, s)
    print(" ".join(map(str, s)))
    koch(n-1, s, u)
    print(" ".join(map(str, u)))
    koch(n-1, u, t)
    print(" ".join(map(str, t)))
    koch(n-1, t, c2)


    

def main():
    fmt = "%.8f %.8f"
    q3 = sqrt(3)

    c1 = [0, 0]
    c2 = [100, 0]

    n = int(input())
    print(fmt % tuple(c1))
    koch(n, c1, c2)
    print(fmt % tuple(c2))

main()

Solution (Python):
def devide2points(p1,p2):
    s=((p1[0]*2+p2[0])/3,(p1[1]*2+p2[1])/3)
    t=((p1[0]+p2[0]*2)/3,(p1[1]+p2[1]*2)/3)
    u=((p1[0]+p2[0])/2-(p2[1]-p1[1])*(3**(1/2))/6,(p1[1]+p2[1])/2+(p2[0]-p1[0])*(3**(1/2))/6)
    return [s,u,t]

def divide(points):
    res = [points[0]]
    for i in range(len(points)-1):
        res = res + devide2points(points[i],points[i+1]) + [points[i+1]]
    return res

n = int(input())
points = [(0.0,0.0),(100.0,0.0)]
for _ in range(n):
    points = divide(points)
for i in points:
    print(i[0],i[1])

Solution (Python):
import math

n = int(input())

def foo(p1, p2):
    s_x = p1[0] + (p2[0] - p1[0]) / 3.0
    s_y = p1[1] + (p2[1] - p1[1]) / 3.0
    t_x = p1[0] + (2 * (p2[0] - p1[0])) / 3.0
    t_y = p1[1] +  (2 * (p2[1] - p1[1])) / 3.0
    u_x = math.cos(math.radians(60)) * (t_x - s_x) - math.sin(math.radians(60)) * (t_y - s_y) + s_x
    u_y = math.sin(math.radians(60)) * (t_x - s_x) + math.cos(math.radians(60)) * (t_y - s_y) + s_y

    return [[s_x, s_y], [u_x, u_y], [t_x, t_y]]

def bar(arr):
    result = []
    for i in range(len(arr) - 1):
        result.append(arr[i])
        result.extend(foo(arr[i], arr[i + 1]))
    result.append(arr[-1])
    return result

result = [[0, 0], [100.0, 0]]

for i in range(n):
    result = bar(result)

for ret in result:
    print("{} {}".format(ret[0], ret[1]))

Solution (Python):
import math

n = int(input())

dots = [[0,0],[100,0]]
for _ in range(n):
    producedDots = []
    for i in range(len(dots)-1):
        pointA = [dots[i][0] + (dots[i+1][0]-dots[i][0])/3, dots[i][1] + (dots[i+1][1]-dots[i][1])/3]
        pointB = [dots[i][0] + (dots[i+1][0]-dots[i][0])*2/3, dots[i][1] + (dots[i+1][1]-dots[i][1])*2/3]

        producedDots.append(dots[i])
        producedDots.append(pointA)

        arrow = [pointB[0]-pointA[0], pointB[1]-pointA[1]]
        cos60 = math.cos(math.radians(60))
        sin60 = math.sin(math.radians(60))
        newArrow = [arrow[0]*cos60 - arrow[1]*sin60, arrow[0]*sin60 + arrow[1]*cos60]
        pointC = [pointA[0] + newArrow[0], pointA[1] + newArrow[1]]
        producedDots.append(pointC)

        producedDots.append(pointB)
    dots = producedDots
    dots.append([100,0])

for _ in dots:
    print(" ".join(map(str,_)))

Solution (Python):
import math

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y


def koch(n, a, b):
    if n == 0:
        return
    th = math.radians(60)
    s = Point((2*a.x+b.x)/3, (2*a.y+b.y)/3)
    t = Point((a.x+2*b.x)/3, (a.y+2*b.y)/3)
    u = Point((t.x-s.x)* math.cos(th) - (t.y-s.y)*math.sin(th)+s.x,
                (t.x-s.x)* math.sin(th) + (t.y-s.y)*math.cos(th)+s.y)

    koch(n-1, a, s)
    print(s.x, s.y)
    koch(n-1, s, u)
    print(u.x, u.y)
    koch(n-1, u, t)
    print(t.x, t.y)
    koch(n-1, t, b)

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())

    a = Point(0, 0)
    b = Point(100, 0)

    print(a.x, a.y)
    koch(n, a, b)
    print(b.x, b.y)

Solution (Python):
def koch(p,q,n):
    if n==0:
        return [p]
    else:
        c1=[(p[0]*2+q[0])/3,(p[1]*2+q[1])/3]
        c3=[(p[0]+q[0]*2)/3,(p[1]+q[1]*2)/3]
        if p[0]<q[0]:
            if p[1]==q[1]:
                c2=[(p[0]+q[0])/2,p[1]+(q[0]-p[0])/2/3**0.5]
            elif p[1]<q[1]:
                c2=[p[0],(p[1]+q[1]*2)/3]
            else:
                c2=[q[0],(p[1]*2+q[1])/3]
        else:
            if p[1]==q[1]:
                c2=c2=[(p[0]+q[0])/2,p[1]+(q[0]-p[0])/2/3**0.5]
            elif p[1]<q[1]:
                c2=[q[0],(p[1]*2+q[1])/3]
            else:
                c2=[p[0],(p[1]+q[1]*2)/3]
        return koch(p,c1,n-1)+koch(c1,c2,n-1)+koch(c2,c3,n-1)+koch(c3,q,n-1)


n=int(input())
ans=koch([0,0],[100,0],n)+[[100,0]]
for i in ans:
    print(*i)

Solution (Python):
n = int(input())
L = [[0,0],[100,0]]
for i in range(n):
    sub = []
    for j in range(len(L)-1):
        K = []
        a = L[j][0]
        b = L[j][1]
        c = L[j+1][0]
        d = L[j+1][1]
        if a == 0:
            K.append([a,b])
        K.append([a+((c-a)/3),b+((d-b)/3)])
        K.append([(a+c)/2+(b-d)*(3**0.5)/6,(b+d)/2+(c-a)*(3**0.5)/6])
        K.append([a+((c-a)*2/3),b+((d-b)*2/3)])
        K.append([c,d])
        sub = sub+K
    L = sub
for i in range(len(L)):
    print(L[i][0],L[i][1])

Solution (Python):
from math import sqrt
from functools import reduce

N = int(input())

def koch(p1, p2, n):
	if n == 0:
		return [p1, p2]
	else:
		c1 = [(2*p1[0] + p2[0])/3, (2*p1[1] + p2[1])/3]
		c3 = [(p1[0] + 2*p2[0])/3, (p1[1] + 2*p2[1])/3]
		c2 = [(p1[0] + p2[0]) / 2 + 1/sqrt(3) * (p1[1] - p2[1])/2, (p1[1] + p2[1]) / 2 + 1/sqrt(3) * (p2[0] - p1[0])/2]
		return koch(p1, c1, n-1)[:-1] + koch(c1, c2, n-1)[:-1] + koch(c2, c3, n-1)[:-1] + koch(c3, p2, n-1)


for p in koch([0.0, 0.0], [100.0, 0.0], N):
	print('{:.6f} {:.6f}'.format(p[0], p[1]))

Solution (Python):
n = int(input())

def drawKoch(p1, p2, i):
    if i == 0:
        print(*p1)
        return 0
    else:
        s = [p2[0]/3+p1[0]*2/3, p2[1]/3+p1[1]*2/3]
        t = [p2[0]*2/3+p1[0]/3, p2[1]*2/3+p1[1]/3]
        u = [p2[0]/2+p1[0]/2-(p2[1]-p1[1])/(2*(3**0.5)), \
            p2[1]/2+p1[1]/2+(p2[0]-p1[0])/(2*(3**0.5))]
        drawKoch(p1, s, i-1)
        drawKoch(s,  u, i-1)
        drawKoch(u,  t, i-1)
        drawKoch(t, p2, i-1)

p1_start = [0.0, 0.0]
p2_start = [100.0, 0.0]
drawKoch(p1_start, p2_start, n)
print(*p2_start)

Solution (Python):
import math
SIN_T = math.sin(math.pi / 3)
COS_T = math.cos(math.pi / 3)


def koch(p0, p4):
    p1 = ((p0[0]*2 + p4[0])/3, (p0[1]*2 + p4[1])/3)
    p3 = ((p0[0] + p4[0]*2)/3, (p0[1] + p4[1]*2)/3)
    p2 = (COS_T*(p3[0]-p1[0]) + -SIN_T*(p3[1]-p1[1]) + p1[0],
          SIN_T*(p3[0]-p1[0]) + COS_T*(p3[1]-p1[1]) + p1[1])

    return [p1, p2, p3, p4]


if __name__ == "__main__":
    n = int(input())
    points = [(0, 0), (100, 0)]

    for _ in [0]*n:
        _points = [points[0]]
        for origin, dest in zip(points, points[1:]):
            _points += koch(origin, dest)

        points = _points

    for p in points:
        print(*p)

Solution (Python):
import math
n = int(input())
pi = math.pi
def distance(p1, p2):
  print(math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2))
  return math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)

def koch(p1, p2):
  p3 = [0, 0]
  p4 = [0, 0]
  p5 = [0, 0]
  p3[0] = round((p1[0]*2 + p2[0]) / 3, 8)
  p3[1] = round((p1[1]*2 + p2[1]) / 3, 8)
  p4[0] = round((p1[0] + p2[0]*2) / 3, 8)
  p4[1] = round((p1[1] + p2[1]*2) / 3, 8)
  p5[0] = round((p4[0]-p3[0])*math.cos(pi/3)-(p4[1]-p3[1])*math.sin(pi/3)+p3[0], 8)
  p5[1] = round((p4[0]-p3[0])*math.sin(pi/3)+(p4[1]-p3[1])*math.cos(pi/3)+p3[1], 8)
  return p3, p4, p5

dots = [[0,0], [100,0]]
def loop(p1, p2, i):
  if i == n:
    return 

  p3, p4, p5= koch(p1, p2)
  dots.append(p3)
  dots.append(p4)
  dots.append(p5)
  loop(p1, p3, i+1)
  print(*p3) 
  loop(p3, p5, i+1)
  print(*p5)
  loop(p5, p4, i+1)
  print(*p4)
  loop(p4, p2, i+1)
  
print(0, 0)
loop([0,0], [100, 0], 0)
print(100, 0)

Solution (Python):
import math
def kochCurve(d, p1, p2):
    if d <= 0:
        return
    s = [(2.0*p1[0]+1.0*p2[0])/3.0, (2.0*p1[1]+1.0*p2[1])/3.0]
    t = [(1.0*p1[0]+2.0*p2[0])/3.0, (1.0*p1[1]+2.0*p2[1])/3.0]
    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]]
    kochCurve(d-1, p1, s)
    print(s[0], s[1])
    kochCurve(d-1, s, u)
    print(u[0], u[1])
    kochCurve(d-1, u, t)
    print(t[0], t[1])
    kochCurve(d-1, t, p2)
n = int(input())
s = [0.00000000, 0.00000000]
e = [100.00000000, 0.00000000]
print(s[0],s[1])
if n != 0:
    kochCurve(n,s,e)
print(e[0],e[1])

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):
import math
n = int(input())

cos60 = math.cos(math.radians(60))
sin60 = math.sin(math.radians(60))


def koch(d, p1, p2):
    if d == 0:
        return
    s = [
        (2.0*p1[0]+1.0*p2[0])/3.0,
        (2.0*p1[1]+1.0*p2[1])/3.0
    ]
    t = [
        (1.0*p1[0]+2.0*p2[0])/3.0,
        (1.0*p1[1]+2.0*p2[1])/3.0
    ]
    u = [
        (t[0]-s[0])*cos60 - (t[1]-s[1])*sin60 + s[0],
        (t[0]-s[0])*sin60 + (t[1]-s[1])*cos60 + s[1]
    ]

    koch(d-1, p1, s)
    print(f"{s[0]} {s[1]}")
    koch(d-1, s, u)
    print(f"{u[0]} {u[1]}")
    koch(d-1, u, t)
    print(f"{t[0]} {t[1]}")
    koch(d-1, t, p2)
    return


print(f"{0} {0}")
koch(n, [0, 0], [100, 0])
print(f"{100} {0}")

Solution (Python):
def koch_curve(point1, point2, N):
    if N == 0:
        print('{:8f} {:8f}'.format(point1[0], point1[1]))
        return
    pointS = ((2 * point1[0] + point2[0]) / 3,
              (2 * point1[1] + point2[1]) / 3)
    pointT = ((point2[0] - point1[0]) / 2 - (point2[1] - point1[1]) / 3.46410161514 + point1[0],
              (point2[0] - point1[0]) / 3.46410161514 + (point2[1] - point1[1]) / 2 + point1[1])
    pointU = ((point1[0] + 2 * point2[0]) / 3,
              (point1[1] + 2 * point2[1]) / 3)
    if N > 1:
        koch_curve(point1, pointS, N - 1)
        koch_curve(pointS, pointT, N - 1)
        koch_curve(pointT, pointU, N - 1)
        koch_curve(pointU, point2, N - 1)
    else:
        print('{:8f} {:8f}'.format(point1[0], point1[1]))
        print('{:8f} {:8f}'.format(pointS[0], pointS[1]))
        print('{:8f} {:8f}'.format(pointT[0], pointT[1]))
        print('{:8f} {:8f}'.format(pointU[0], pointU[1]))


N = int(input())
koch_curve((0.0, 0.0), (100.0, 0.0), N)
print('100.00000000 0.00000000')

Solution (Python):
import cmath

cmp_s = cmath.rect(1/3, 0)
cmp_u = cmath.rect(3**(-1/2), cmath.pi / 6)
cmp_t = cmath.rect(2/3, 0)


def koch_curve(p1: complex, p2: complex, n):
    if n != 0:
        cmp = p2 - p1
        s, u, t = [p1 + cmp * c for c in (cmp_s, cmp_u, cmp_t)]
        koch_curve(p1, s, n-1)
        print('{0:8f} {1:8f}'.format(s.real, s.imag))
        koch_curve(s, u, n-1)
        print('{0:8f} {1:8f}'.format(u.real, u.imag))
        koch_curve(u, t, n-1)
        print('{0:8f} {1:8f}'.format(t.real, t.imag))
        koch_curve(t, p2, n-1)


def main():
    n = int(input())
    print('{0:8f} {1:8f}'.format(.0, .0))
    koch_curve(complex(.0, .0), complex(100.0, .0), n)
    print('{0:8f} {1:8f}'.format(100.0, .0))


if __name__ == '__main__':
    main()

Solution (Python):

import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
def drawKoch(p1, p2, N):
    s = Point((2*p1.x+p2.x)/3,(2*p1.y+p2.y)/3)
    t = Point((p1.x+2*p2.x)/3,(p1.y+2*p2.y)/3)
    xx = t.x - s.x
    yy = t.y - s.y
    u = Point(s.x + xx/2 - yy*math.sqrt(3)/2, s.y + xx*math.sqrt(3)/2 + yy/2)
    if N > 1:
        drawKoch(p1, s, N-1)
        drawKoch(s, u, N-1)
        drawKoch(u, t, N-1)
        drawKoch(t, p2, N-1)
    else:
        printPoint(p1)
        printPoint(s)
        printPoint(u)
        printPoint(t)

def printPoint(p):
    print("{0:.8f} {1:.8f}".format(p.x, p.y))

n = int(input().rstrip())
p1 = Point(0,0)
p2 = Point(100,0)
if n == 0:
    printPoint(p1)
    printPoint(p2)
else:
    drawKoch(p1, p2, n)
    printPoint(p2)

Solution (Python):
import math

def triangle(co1, co2):
    ans = []
    x1 = co1[0]
    y1 = co1[1]
    x2 = co2[0]
    y2 = co2[1]
    part1 = [(2 * x1 + x2) /3, (2 * y1 + y2) / 3]
    part2 = [(x1 + 2 * x2) /3, (y1 + 2 * y2) / 3]
    
    edge = [(part2[0] - part1[0])/2 - (part2[1] - part1[1])/ 2 * math.sqrt(3) + part1[0], (part2[0] - part1[0])/2 * math.sqrt(3) + (part2[1] - part1[1])/ 2 + part1[1]]
    ans.extend([part1, edge, part2, co2])
    return ans
def rec(A, n):
    if n == 0:
        return
    
    rec(A, n-1)
    for i in range(4 ** (n-1)):
        A[n].extend(triangle(A[n-1][i], A[n-1][i+1]))

n = int(input())
koch = [[[0.0, 0.0]] for i in range(n + 1)]
koch[0].append([100.0, 0.0])
rec(koch, n)
for i in range(4 ** n + 1):
    print(*koch[n][i])

Solution (Python):
import sys, math
input = sys.stdin.readline

def print_tuple(t):
    print('{} {}'.format(t[0], t[1]))

def describe(depth, p1, p2):
    if(depth == 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_x = (t[0] - s[0]) * math.cos(math.radians(60)) - (t[1] - s[1]) * math.sin(math.radians(60)) + s[0]
    u_y = (t[0] - s[0]) * math.sin(math.radians(60)) + (t[1] - s[1]) * math.cos(math.radians(60)) + s[1]
    u = (u_x, u_y)

    describe(depth - 1, p1, s)
    print_tuple(s)
    describe(depth - 1, s, u)
    print_tuple(u)
    describe(depth - 1, u, t)
    print_tuple(t)
    describe(depth - 1, t, p2)

N = int(input())
start = (0.0, 0.0)
end = (100., 0.)
print_tuple(start)
describe(N, start, end)
print_tuple(end)

Solution (Python):
from sys import stdin
from math import sin, cos, pi

def kock(n, p1, p2):
    if n != 0:
        s = ( (2.0*p1[0]+p2[0])/3.0, (2.0*p1[1]+p2[1])/3.0 )
        t = ( (p1[0]+2.0*p2[0])/3.0, (p1[1]+2.0*p2[1])/3.0 )
        u_x = (t[0]-s[0])*cos(pi/3.0) - (t[1]-s[1])*sin(pi/3.0) + s[0]
        u_y = (t[0]-s[0])*sin(pi/3.0) + (t[1]-s[1])*cos(pi/3.0) + s[1]
        u = (u_x, u_y)

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

n = int(stdin.readline().rstrip())
p1 = (0.0, 0.0)
p2 = (100.0, 0.0)
print(*p1)
kock(n, p1, p2)
print(*p2)

Solution (Python):
from math import sin, cos, radians


def c(l, p1, p2):
    l -= 1
    if l < 0:
        return
    s = ((p1[0] * 2 + p2[0]) / 3, (p1[1] * 2 + p2[1]) / 3)
    c(l, p1, s)
    print(s[0], s[1])
    t = ((p1[0] + p2[0] * 2) / 3, (p1[1] + p2[1] * 2) / 3)
    dx = t[0] - s[0]
    dy = t[1] - s[1]
    u = (dx * c60 - dy * s60 + s[0], dx * s60 + dy * c60 + s[1])
    c(l, s, u)
    print(u[0], u[1])
    c(l, u, t)
    print(t[0], t[1])
    c(l, t, p2)


r = radians(60)
s60 = sin(r)
c60 = cos(r)
print(0, 0)
c(int(input()), (0, 0), (100, 0))
print(100, 0)

Solution (Python):

import math

class KochCurve(object):
	
	x = 0.0
	y = 0.0

	
	

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

		s = KochCurve()
		t = KochCurve()
		u = KochCurve()
		th = math.pi * 60.0 / 180.0

		s.x = (2.0 * a.x + 1.0 * b.x) / 3.0
		s.y = (2.0 * a.y + 1.0 * b.y) / 3.0
		t.x = (1.0 * a.x + 2.0 * b.x) / 3.0
		t.y = (1.0 * a.y + 2.0 * b.y) / 3.0
		u.x = (t.x - s.x) * math.cos(th) - (t.y - s.y) * math.sin(th) + s.x
		u.y = (t.x - s.x) * math.sin(th) + (t.y - s.y) * math.cos(th) + s.y
		
		KochCurve().koch(n - 1, a, s)
		msg = "%.8f %.8f" % (s.x, s.y)
		print(msg)
		KochCurve().koch(n - 1, s, u)
		msg = "%.8f %.8f" % (u.x, u.y)
		print(msg)
		KochCurve().koch(n - 1, u, t)
		msg = "%.8f %.8f" % (t.x, t.y)
		print(msg)
		KochCurve().koch(n - 1, t, b)


if __name__ == '__main__':
	a = KochCurve()
	b = KochCurve()

	n = int(input())

	a.x = 0
	a.y = 0
	b.x = 100
	b.y = 0

	msg = "%.8f %.8f" % (a.x, a.y)
	print(msg)
	KochCurve().koch(n, a, b)
	msg = "%.8f %.8f" % (b.x, b.y)
	print(msg)

Solution (Python):
import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return "{:.8f} {:.8f}".format(self.x, self.y)

class kochCurveController:
    def insertTriangle(self,p1, p2,d):
        if d == 0:
            return
        s = self.secret(p1,p2,1,2)
        t = self.secret(p1,p2,2,1)
        u = self.calcVertex(s,t)

        self.insertTriangle(p1,s,d-1)
        print(s)
        self.insertTriangle(s,u,d-1)
        print(u)
        self.insertTriangle(u,t,d-1)
        print(t)
        self.insertTriangle(t,p2,d-1)


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

    def secret(self,va,vb,a,b):
        return Point((b*(va.x)+a*(vb.x))/(a+b),(b*(va.y)+a*(vb.y))/(a+b))


K = kochCurveController()
N = int(input())
print(Point(0,0))
K.insertTriangle(Point(0,0),Point(100,0),N)
print(Point(100,0))

Solution (Python):
from math import sin, cos, radians

depth = int(input())


def kock(n: int, p1x: float, p1y: float, p2x: float, p2y: float)-> None:
    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
    ux = (tx - sx) * cos(radians(60)) - (ty - sy) * sin(radians(60)) + sx
    uy = (tx - sx) * sin(radians(60)) + (ty - sy) * cos(radians(60)) + sy
    kock(n - 1, p1x, p1y, sx, sy)
    print(f'%10.7f %10.7f' % (sx, sy))
    kock(n - 1, sx, sy, ux, uy)
    print(f'%10.7f %10.7f' % (ux, uy))
    kock(n - 1, ux, uy, tx, ty)
    print(f'%10.7f %10.7f' % (tx, ty))
    kock(n - 1, tx, ty, p2x, p2y)


print(f'%1.7f %1.7f' % (0.0, 0.0))
kock(depth, 0.0, 0.0, 100.0, 0.0)
print(f'%10.7f %10.7f' % (100.0, 0.0))

Solution (Python):
import math

def rot60(s, t):
    v = t - s
    a = 1/2 + complex(0,(math.sqrt(3)/2))
    return v * a + s

def pr(p):
    x = p.real
    y = p.imag
    print('%.10f %.10f'%(x, y))

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

    s = (p2 - p1) * (1/3) + p1
    t = (p2 - p1) * (2/3) + p1
    u = rot60(s, t)
    dfs(p1, s, n - 1)
    pr(s)
    dfs(s, u, n - 1)
    pr(u)
    dfs(u, t, n - 1)
    pr(t)
    dfs(t, p2, n -1)
    
n = int(input())
s = (0 + 0j)
t = (100 + 0j)
pr(s)
dfs(s, t, n) 
pr(t)

Solution (Python):
import sys
import math


def koch(p1, p2):
    d = ((p2[0] - p1[0]) / 3, (p2[1] - p1[1]) / 3)
    s = (p1[0] + d[0], p1[1] + d[1])
    t = (p1[0] + d[0] * 2, p1[1] + d[1] * 2)
    u = (
        s[0] + (1 / 2) * d[0] - (math.sqrt(3) / 2) * d[1],
        s[1] + (math.sqrt(3) / 2) * d[0] + (1 / 2) * d[1]
    )
    return [p1, s, u, t]


ps = [(0, 0), (100, 0)]
n = int(sys.stdin.readline())
for _ in range(n):
    points = []
    for i in range(len(ps) - 1):
        points += koch(ps[i], ps[i + 1])
    points += [ps[-1]]
    ps = points

for p in ps:
    print(' '.join('{0:.8f}'.format(x) for x in p))

Solution (Python):






import sys
input = sys.stdin.readline
import cProfile
from math import cos,sin,radians

t = set()
def koch(n,st,ed):
    if (n == 0 ):
        print ('{:.8f} {:.8f}'.format(*ed))
        return
    s1 = st
    s5 = ed
    (x1,y1) = st
    (x5,y5) = ed

    x2 = x1 + (x5 - x1) / 3.0
    y2 = y1 + (y5 - y1)  / 3.0
    s2 = (x2,y2)

    x4 = x1 + ((x5 -x1 ) / 3.0 ) * 2
    y4 = y1 + ((y5 - y1) / 3.0 ) * 2
    s4 = (x4,y4)

    x3 = (x4-x2) * cos(radians(60)) - (y4-y2 ) * sin(radians(60)) + x2
    y3 = (x4-x2) * sin(radians(60)) + (y4-y2 ) * cos(radians(60)) + y2
    s3 = (x3,y3)

    t.add(s1)
    t.add(s2)
    t.add(s3)
    t.add(s4)
    t.add(s5)
    
    koch (n-1,s1,s2)
    
    koch (n-1,s2,s3)
    
    koch (n-1,s3,s4)
    
    koch (n-1,s4,s5)
    

def main():
    n = int(input())




    print ('{:.8f} {:.8f}'.format(0,0))
    koch(n,(0,0),(100,0))




if __name__ == '__main__':
    main()

Solution (Python):
def next_koch(n):
    turn60 = 0.5 + 3 ** 0.5 * 0.5j
    n_next = [n[0]]
    for i in range(1, len(n)):
        s = (n[i - 1] * 2 + n[i]) / 3
        t = (n[i - 1] + n[i] * 2) / 3
        u = (t - s) * turn60 + s
        n_next +=[s, u, t, n[i]]
    return n_next

p1 = 0 + 0j
p2 = 100 + 0j
koch = [p1, p2]

n = int(input())
for i in range(n):
    koch = next_koch(koch)

for z in koch:
    print("{:.8f} {:.8f}".format(z.real, z.imag))

Solution (Python):
import math
def show_vertex(x,y):
    print("%.8f %.8f" % (x,y))
def koch(x0,y0,x1,y1,n):
    if n == 0:
        show_vertex(x0,y0)
    else:
        c1 = [(2*x0+x1)/3,(2*y0+y1)/3]
        c3 = [(x0+2*x1)/3,(y0+2*y1)/3]
        c2 = [(3*(x1+x0) -(y1-y0)*math.sqrt(3))/6,((x1-x0)*math.sqrt(3)+3*(y1+y0))/6]
        koch(x0,y0,c1[0],c1[1],n-1)
        koch(c1[0],c1[1],c2[0],c2[1],n-1)
        koch(c2[0],c2[1],c3[0],c3[1],n-1)
        koch(c3[0],c3[1],x1,y1,n-1)
N = int(input())
koch(0,0,100,0,N)
show_vertex(100,0)

Solution (Python):
import math
import copy
def koch(x1,y1,x2,y2):
    x3,y3 = (x1*2+x2)/3, (y1*2+y2)/3
    x4,y4 = (x1+x2*2)/3, (y1+y2*2)/3
    x5, y5 = x3 + (x4-x3)/2-((y4-y3)*math.sqrt(3))/2, y3 + ((x4-x3)*math.sqrt(3))/2+(y4-y3)/2
    return x3, y3, x4, y4, x5, y5

n = int(input())
a = [[0,0],[100,0]]
b = copy.copy(a)
for _ in range(n):
    b = copy.copy(a)
    for i in range(len(b)-1):
        x3,y3,x4,y4,x5,y5 = koch(b[i][0],b[i][1],b[i+1][0],b[i+1][1])
        a.insert(4*i+1,[x3,y3])
        a.insert(4*i+2, [x5,y5])
        a.insert(4*i+3, [x4,y4])

for i in a:
    i = list(map(str, i))
    print(' '.join(i))

Solution (Python):
import math
n = int(input())
pi = math.acos(-1)
th = pi/3


class point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


def koch(n, a, b):
        if n == 0:
            return 0
        s = point((2*a.x+1*b.x)/3, (2*a.y+1*b.y)/3)
        t = point((1*a.x+2*b.x)/3, (1*a.y+2*b.y)/3)
        u = point((t.x-s.x)*math.cos(th)
                  - (t.y-s.y)*math.sin(th)+s.x,
                  (t.x-s.x)*math.sin(th)+(t.y-s.y)*math.cos(th)+s.y)
        koch(n-1, a, s)
        print("{:.8f} {:.8f}".format(s.x, s.y))
        koch(n-1, s, u)
        print("{:.8f} {:.8f}".format(u.x, u.y))
        koch(n-1, u, t)
        print("{:.8f} {:.8f}".format(t.x, t.y))
        koch(n-1, t, b)


a = point(round(0, 8), round(0, 8))
b = point(round(100, 8), round(0, 8))
print("{:.8f} {:.8f}".format(a.x, a.y))
koch(n, a, b)
print("{:.8f} {:.8f}".format(b.x, b.y))

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop



BIG_NUM = 2000000000
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001


def MIN(A,B):
    if A <= B:
        return A
    else:
        return B

def MAX(A,B):
    if A >= B:
        return A
    else:
        return B



class Point:
    def __init__(self,arg_x,arg_y):
        self.x = arg_x
        self.y = arg_y


def roll(div1,div2):
    tmp_start = Point(div2.x-div1.x,div2.y-div1.y)
    tmp_end = Point(tmp_start.x*math.cos(math.pi/3) -tmp_start.y*math.sin(math.pi/3),
                    tmp_start.x*math.sin(math.pi/3) + tmp_start.y*math.cos(math.pi/3))
    ret = Point(tmp_end.x + div1.x,tmp_end.y + div1.y)
    return ret;


def outPut(point):
    print("%.8f %.8f"%(point.x,point.y))


def calc(left,right,count):
    div1 = Point((2*left.x + right.x)/3,(2*left.y + right.y)/3)
    div2 = Point((2*right.x + left.x)/3,(2*right.y + left.y)/3)
    peek = roll(div1,div2)

    if count > 1:
        calc(left,div1,count-1)
        calc(div1,peek,count-1)
        calc(peek,div2,count-1)
        calc(div2,right,count-1)
    else:
        outPut(left);
        outPut(div1);
        outPut(peek);
        outPut(div2);


N = int(input())
left = Point(0,0)
right = Point(100,0)

if N == 0:
    outPut(left)
    outPut(right)
else:
    calc(left,right,N)
    outPut(right)

Solution (Python):
import math


def koch(k, p1, p2):
    if k==0:
        print('{0:.8f} {1:.8f}'.format(p1[0],p1[1]))

    s = [p1[0]*2/3+p2[0]/3, p1[1]*2/3+p2[1]/3]
    u = [(p1[0]+p2[0])/2+(p1[1]-p2[1])*math.sqrt(3)/6,
         (p1[1]+p2[1])/2+(p2[0]-p1[0])*math.sqrt(3)/6]
    t = [p1[0]/3+p2[0]*2/3, p1[1]/3+p2[1]*2/3]
    if k==1:
        print('{0:.8f} {1:.8f}'.format(p1[0],p1[1]))
        print('{0:.8f} {1:.8f}'.format(s[0],s[1]))
        print('{0:.8f} {1:.8f}'.format(u[0],u[1]))
        print('{0:.8f} {1:.8f}'.format(t[0],t[1]))
    elif k>0:
        koch(k-1,p1,s)
        koch(k-1,s,u)
        koch(k-1,u,t)
        koch(k-1,t,p2)
    if k==n:
        print('{0:.8f} {1:.8f}'.format(p2[0],p2[1]))

n = int(input())
koch(n, [0,0],[100,0])

Solution (Python):

from math import pi, cos, sin
    
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __str__(self):
        return str(self.x) + " " + str(self.y)
        
    def __add__(self, p):
        return Point(self.x + p.x, self.y + p.y)
    
    def __sub__(self, p):
        return Point(self.x - p.x, self.y - p.y)
    
    def __mul__(self, scala):
        return Point(self.x * scala, self.y * scala)
        
    def __div__(self, scala):
        return Point(self.x / scala, self.y / scala)
        
    def __truediv__(self, scala):
        return self.__div__(scala)
    
    def rotate(self, theta: float, origin: "Point"):
        if origin == None:
            origin = Point(0, 0)
        _self = self - origin
        x = _self.x * cos(theta) - _self.y * sin(theta)
        y = _self.x * sin(theta) + _self.y * cos(theta)        
        return Point(x, y) + origin


def dump(points: [Point]):
    for p in points:
        print(p)
        

def koch(points: [Point], n: int) -> [Point]:
    if n <= 0: return points
    if len(points) <= 1: return points
    
    _points = __koch(points)
    return koch(_points[0:2], n - 1) + \
        koch(_points[1:3], n - 1)[1:] + \
        koch(_points[2:4], n - 1)[1:] + \
        koch(_points[3:5], n - 1)[1:]


def tertile(pair: [Point, Point]) -> [Point, Point, Point, Point]:
    t1 = pair[0] + (pair[1] - pair[0]) / 3;
    t2 = pair[0] + (pair[1] - pair[0]) * 2 / 3;
    return [pair[0], t1, t2, pair[1]];
    

def __koch(pair: [Point, Point]) -> [Point, Point, Point, Point, Point]:
    four = tertile(pair)
    mid = four[1].rotate(-pi/3, four[2])
    return four[:2] + [mid] + four[2:]
        
def main():
    points = [Point(0, 0), Point(100, 0)]
    dump(koch(points, int(input())))
    

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
sin60 = 3 ** 0.5 / 2
cos60 = 1 / 2

def kach(d, A, B):
    if d == n:
        print('{0:.8f} {1:.8f}'.format(*B))
        return True
    x0, y0 = A
    x1, y1 = B

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

    sx = x0 + dx
    sy = y0 + dy

    tx = x0 + 2 * dx
    ty = y0 + 2 * dy

    ux = sx + (dx * cos60 - dy * sin60)
    uy = sy + (dx * sin60 + dy * cos60)

    S, T, U = (sx, sy), (tx, ty), (ux, uy)
    d += 1
    kach(d, A, S), kach(d, S, U), kach(d, U, T), kach(d, T, B)
start = (0.0, 0.0)
end = (100.0, 0.0)
print('{0:.8f} {1:.8f}'.format(*start))
kach(0, start, end)

Solution (Python):

"""
Created on Sat Sep 22 14:29:49 2018

@author: maezawa
"""

n = int(input())

p0 = [0, 0]
p1 = [100, 0]

def koch(edge):
    
    p0 = edge[0]
    p1 = edge[1]
    s = [0,0]
    t = [0,0]
    u = [0,0]
    u1 = [0,0]
    u2 = [0,0]
    s[0] = (p1[0] - p0[0])/3 + p0[0] 
    s[1] = (p1[1] - p0[1])/3 + p0[1]
    t[0] = (p1[0] - p0[0])*2/3 +p0[0]
    t[1] = (p1[1] - p0[1])*2/3 +p0[1]
    u1[0] = (p0[0] + p1[0])/2
    u1[1] = (p0[1] + p1[1])/2
    u2[0] = p0[1]-s[1]
    u2[1] = s[0]-p0[0]
    u[0] = u1[0] + u2[0]*3**0.5/2
    u[1] = u1[1] + u2[1]*3**0.5/2
    return([p0,s,u,t,p1])

points = [p0, p1]

for i in range(n):
    nextpoints = []
    for edge in zip(points, points[1:]):
        k = koch(edge)
        kl = k.pop(-1)
        nextpoints.extend(k)
    nextpoints.append(kl)   
    points = nextpoints

for i in range(len(points)):
    print(*points[i], sep=' ')

Solution (Python):



from math import pi
from cmath import rect

def fromPolar(r, theta):
    return r * complex(cos(theta), sin(theta))

def print_xy(z):
    print(z.real, z.imag)

def koch(p1, p2, level):
    if level == 0:
        return
    l = p2 - p1
    s = p1 + (1/3) * l
    t = p1 + (2/3) * l
    u = s + (1/3) * l * rect(1, pi/3)
    koch(p1, s, level - 1)
    print_xy(s)
    koch(s, u, level - 1)
    print_xy(u)
    koch(u, t, level - 1)
    print_xy(t)
    koch(t, p2, level - 1)

def main():
    n = int(input())
    print_xy(0+0j)
    koch(0+0j, 100+0j, n)
    print_xy(100+0j)

main()

Solution (Python):
import math

global th
th = math.pi * (60/180)

def koch(d, p1, p2):
    if d == 0:
        return
    else:
        s_x = (2 * p1[0] + p2[0]) / 3
        s_y = (2 * p1[1] + p2[1]) / 3
        s = (s_x, s_y)
        t_x = (p1[0] + 2 * p2[0]) / 3
        t_y = (p1[1] + 2 * p2[1]) / 3
        t = (t_x, t_y)
        u_x = (t[0] - s[0]) * math.cos(th) - (t[1] - s[1]) * math.sin(th) + s[0]
        u_y = (t[0] - s[0]) * math.sin(th) + (t[1] - s[1]) * math.cos(th) + s[1]
        u = (u_x, u_y)

        koch(d-1, p1, s)
        print(*s, sep=" ")
        koch(d-1, s, u)
        print(*u, sep=" ")
        koch(d-1, u, t)
        print(*t, sep=" ")
        koch(d-1, t, p2)

n = int(input())
p1 = (0.0, 0.0)
p2 = (100.0, 0.0)
print(*p1, sep=" ")
koch(n, p1, p2)
print(*p2, sep=" ")