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 sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
ans = []
class P:
    def __init__(self,x,y):
        self.x = x
        self.y = y
    
    def __str__(self):
        return str(self.x) + " " + str(self.y)
    __repr__ = __str__
    

    def __add__(self,p):
        return P(self.x+p.x, self.y+p.y)
    
    __radd__ = __add__
        
    def __sub__(self, p):
        return P(self.x-p.x, self.y-p.y)

    def __mul__(self,other):
        return P(self.x*other, self.y*other)

    def __truediv__(self, other):
        return P(self.x/other, self.y/other)

    
    
    
    
    


def koch(n,left,right):
    if n==0:
        return 
    w = ((right-left)/3)
    s = left + w
    t = left + w*2
    center = (s+t)/2 
    vec1 = (t-s)*sqrt(3)/2 
    vec2 = P(-vec1.y, vec1.x) 
    u = center + vec2

    
    koch(n-1,left, s)
    print(s)
    koch(n-1, s, u)
    print(u)
    koch(n-1,u,t)
    print(t)
    koch(n-1,t,right)
    
    


    
    
    
def main():
    n = int(input())
    left = P(0,0)
    right = P(100,0)
    print(left)
    koch(n,P(0,0),P(100,0))
    print(right)
    
if __name__ == '__main__':
    main()

Solution (Python):
import math

def KochCurve(p1,p2,n):
    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 = [(p1[0]+p2[0])/2+((-1)*math.sqrt(3))*(p2[1]-p1[1])/6,(p1[1]+p2[1])/2+(math.sqrt(3))*(p2[0]-p1[0])/6]
    KochCurve(p1,s,n-1)
    print(f"{'{:.9f}'.format(s[0])} {'{:.9f}'.format(s[1])}")
    KochCurve(s,u,n-1)
    print(f"{'{:.9f}'.format(u[0])} {'{:.9f}'.format(u[1])}")
    KochCurve(u,t,n-1)
    print(f"{'{:.9f}'.format(t[0])} {'{:.9f}'.format(t[1])}")
    KochCurve(t,p2,n-1)

p1 = [0,0]
p2 = [100,0]
n = int(input())
print(f"{'{:.9f}'.format(p1[0])} {'{:.9f}'.format(p1[1])}")
KochCurve(p1,p2,n)
print(f"{'{:.9f}'.format(p2[0])} {'{:.9f}'.format(p2[1])}")

Solution (Python):
import math

d = int(input())

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

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

def koch(d, p1, p2):
    pi = math.pi
    cos60 = math.cos(pi/3)
    sin60 = math.sin(pi/3)
    if d == 0:
        return
    else:
        s = point((2*p1.x + 1*p2.x)/3, (2*p1.y + 1*p2.y)/3)
        t = point((1*p1.x + 2*p2.x)/3, (1*p1.y + 2*p2.y)/3)
        u = point(s.x + cos60*(t.x-s.x) - sin60*(t.y-s.y), s.y + sin60*(t.x-s.x) + cos60*(t.y-s.y))
        koch(d-1, p1, s)
        print(s.x, s.y)
        koch(d-1, s, u)
        print(u.x, u.y)
        koch(d-1, u, t)
        print(t.x, t.y)
        koch(d-1, t, p2)

print(p1.x, p1.y)
koch(d, p1, p2)
print(p2.x, p2.y)

Solution (Python):
def koch(p1,p2):
    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]
    m=[(p1[0]+p2[0])/2,(p1[1]+p2[1])/2]
    mu=[-(p2[1]-p1[1])*3**.5/6,(p2[0]-p1[0])*3**.5/6]
    u=[m[0]+mu[0],m[1]+mu[1]]
    return [s,u,t]
ans=[[0,0],[100,0]]
n=int(input())
for _ in range(n):
    now=ans.copy()
    ans=[]
    l=0
    r=1
    c=len(now)
    while r<c:
        ans.append(now[l])
        ans+=koch(now[l],now[r])
        l+=1
        r+=1
    ans.append(now[l])
for p in ans:
    print(*p)

Solution (Python):
def rec(A,n):
    if n==0:
        return A
    else:
        return rec(draw(A),n-1)

def draw(A):
    l=[]
    for i in range(len(A)-1):
        a=(A[i+1][0]-A[i][0])/3
        b=(A[i+1][1]-A[i][1])/3
        u0=(a,b)
        u60=(a*(1/2)-b*(3**(1/2)/2),a*(3**(1/2)/2)+b*(1/2))
        u300=(a*(1/2)+b*(3**(1/2)/2),-a*(3**(1/2)/2)+b*(1/2))
        
        P=(A[i][0]+u0[0],A[i][1]+u0[1])
        Q=(P[0]+u60[0],P[1]+u60[1])
        R=(Q[0]+u300[0],Q[1]+u300[1])

        l.extend([A[i],P,Q,R])
    l.append(A[-1])   
    return l

n=int(input())
A=[(0.0,0.0),(100.0,0.0)]
B=rec(A,n)

for P in B:
    print(f'{P[0]} {P[1]}')

Solution (Python):

import sys

import math

input = sys.stdin.readline
n = int(input())

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

k = ([[cos60, -(sin60)], [sin60, cos60]])


def main():
    start = [0.00000000, 0.00000000]
    end = [100.00000000, 0.00000000]
    print(' '.join(map(str, start)))
    Koch(start, end, 0)
    print(' '.join(map(str, end)))


def Koch(start, end, layer):
    layer += 1
    if layer > n:
        return
    point1 = [((end[0] - start[0]) / 3) + start[0], ((end[1] - start[1]) / 3) + start[1]]
    Koch(start, point1, layer)
    print(' '.join(map(str, point1)))
    point3 = [((end[0] - start[0]) / 3 * 2) + start[0], ((end[1] - start[1]) / 3 * 2) + start[1]]
    
    vec = ([[point3[0] - point1[0]], [point3[1] - point1[1]]])  
    point2 = [[k[0][0] * vec[0][0] + k[0][1] * vec[1][0]], [k[1][0] * vec[0][0] + k[1][1] * vec[1][0]]]  
    point2 = [point2[0][0] + point1[0], point2[1][0] + point1[1]]  
    Koch(point1, point2, layer)
    print(' '.join(map(str, point2)))
    Koch(point2, point3, layer)
    print(' '.join(map(str, point3)))
    Koch(point3, end, layer)


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
n = int(input())
a = [0] * 2
b = [0] * 2
a[0] = 0
b[0] = 100

def koch(n, a, b):
    if n == 0:
        return
    
    s = [0] * 2
    t = [0] * 2
    u =[0] * 2
    
    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(math.pi/3) - (t[1] - s[1]) * math.sin(math.pi/3) + s[0]
    u[1] = (t[0] - s[0]) * math.sin(math.pi/3) + (t[1] - s[1]) * math.cos(math.pi/3) + s[1]
    
    koch(n - 1, a, 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, b)

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

Solution (Python):
import math

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

	def __repr__(self):
		return "%.8f %.8f"%(self.x, self.y)


def koch(d, a, b):
	th = math.pi * 60.0 / 180.0
	if d == 0:
		return 0
	else:
		s = Point((2 * a.x + b.x) / 3.0, (2 * a.y + b.y) / 3.0)
		t = Point((a.x + 2 * b.x) / 3.0, (a.y + 2 * b.y) / 3.0)
		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(d-1, a, s)
		print(s)
		koch(d-1, s, u)
		print(u)
		koch(d-1, u, t)
		print(t)
		koch(d-1, t, b)


if __name__ == "__main__":
	n = int(input())
	p1 = Point(0.0, 0.0)
	p2 = Point(100.0, 0.0)
	print(p1)
	koch(n, p1, p2)
	print(p2)

Solution (Python):

n = int(input())

p1, p2 = (0, 0), (100, 0)
ans_ls = [p1, p2]


def koch(d, p1, p2):
    '''
    d...現在の深さ 0スタートにする
    p1,p2...端の座標。ここから途中の座標を計算しlistにappendする
    '''
    
    if d == n:
        return

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

    
    
    R = [[1/2, -0.86602540378], [0.86602540378, 1/2]]
    u = (R[0][0] * (t[0] - s[0]) + R[0][1] * (t[1] - s[1]) + s[0],
         R[1][0] * (t[0] - s[0]) + R[1][1] * (t[1] - s[1]) + s[1])
    ans_ls.extend([s, u, t])  

    
    koch(d+1, p1, s)
    print(*s)
    koch(d+1, s, u)
    print(*u)
    koch(d+1, u, t)
    print(*t)
    koch(d+1, t, p2)


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

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

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

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

    s = Coordinate((2*p1.x+p2.x)/3, (2*p1.y+p2.y)/3)
    t = Coordinate((p1.x+2*p2.x)/3, (p1.y+2*p2.y)/3)
    ux = (t.x-s.x)*cos(pi/3) - (t.y-s.y)*sin(pi/3) + s.x
    uy = (t.x-s.x)*sin(pi/3) + (t.y-s.y)*cos(pi/3) + s.y
    u = Coordinate(ux, uy)
    
    kock(n-1, p1, s)
    print("%f %f"%(s.x, s.y))
    kock(n-1, s, u)
    print("%f %f"%(u.x, u.y))
    kock(n-1, u, t)
    print("%f %f"%(t.x, t.y))
    kock(n-1, t, p2)
    
n = int(input())
p1 = Coordinate(0, 0)
p2 = Coordinate(100, 0)

print("%f %f"%(p1.x, p2.y))
kock(n, p1, p2)
print("%f %f"%(p2.x, p2.y))

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

P = [(0.0,0.0), (100.0, 0)]

import copy
import math
sin60 = math.sin(math.radians(60))
cos60 = math.cos(math.radians(60))
for _ in range(n):
    next_p = []
    for p1, p2 in zip(P[:-1], P[1:]):
        l = (p1[0]*2/3+p2[0]*1/3, p1[1]*2/3+p2[1]*1/3) 
        r = (p1[0]*1/3+p2[0]*2/3, p1[1]*1/3+p2[1]*2/3)
        x = cos60*(r[0]-l[0])-sin60*(r[1]-l[1])+l[0]
        y = sin60*(r[0]-l[0])+cos60*(r[1]-l[1])+l[1]
        next_p.append(p1)
        next_p.append(l)
        next_p.append((x, y))
        next_p.append(r)
    next_p.append(P[-1])
    P = copy.copy(next_p)

for p in P:
    print(p[0], p[1])

Solution (Python):

import math

def koch(i, p, q):
    if i == n:
        print(' '.join(map(str, p)))
        if q[0] == 100:
            print(' '.join(map(str, q)))
        return

    x1 = (2 * p[0] + q[0]) / 3
    y1 = (2 * p[1] + q[1]) / 3
    x2 = (p[0] + 2 * q[0]) / 3
    y2 = (p[1] + 2 * q[1]) / 3

    x3 = math.cos(math.radians(60)) * (x2 - x1) - math.sin(math.radians(60)) * (y2 - y1) + x1
    y3 = math.sin(math.radians(60)) * (x2 - x1) + math.cos(math.radians(60)) * (y2 - y1) + y1

    koch(i + 1, p, [x1, y1])
    koch(i + 1, [x1, y1], [x3, y3])
    koch(i + 1, [x3, y3], [x2, y2])
    koch(i + 1, [x2, y2], q)


n = int(input())

koch(0, [0, 0], [100, 0])

Solution (Python):
def rev(s, t):
    xa, ya = s
    xb, yb = t
    X = xb - xa
    Y = yb - ya

    return (X - (3 ** 0.5) * Y) / 2 + xa, (Y + (3 ** 0.5) * X) / 2 + ya


def f(n):
    print(0, 0)
    _f((0, 0), (100, 0), 0, n - 1)
    print(100, 0)


def _f(p1, p2, n, end):

    if n > end:
        return
    xa, ya = p1
    xb, yb = p2
    s = xa + (xb - xa) / 3, ya + (yb - ya) / 3
    t = xa + (xb - xa) * 2 / 3, ya + (yb - ya) * 2 / 3
    u = rev(s, t)
    _f(p1, s, n + 1, end)
    print(s[0], s[1])
    _f(s, u, n + 1, end)
    print(u[0], u[1])
    _f(u, t, n + 1, end)
    print(t[0], t[1])
    _f(t, p2, n + 1, end)


def main():
    f(int(input()))


if __name__ == '__main__':
    main()

Solution (Python):
import math

def koch(n, ax, ay, bx, by):
    if n == 0: return ;
    
    sin = math.sin(math.radians(60))
    cos = math.cos(math.radians(60))
    
    sx = (2.0 * ax + 1.0 * bx) / 3.0
    sy = (2.0 * ay + 1.0 * by) / 3.0
    tx = (1.0 * ax + 2.0 * bx) / 3.0
    ty = (1.0 * ay + 2.0 * by) / 3.0
    ux = (tx - sx) * cos - (ty - sy) * sin + sx
    uy = (tx - sx) * sin + (ty - sy) * cos + sy
    
    koch(n-1, ax, ay, sx, sy)
    print(str(sx)+ " " + str(sy))
    koch(n-1, sx, sy, ux, uy)
    print(str(ux)+ " " + str(uy))
    koch(n-1, ux, uy, tx, ty)
    print(str(tx)+ " " + str(ty))
    koch(n-1, tx, ty, bx, by)

if __name__ == '__main__':
    n = int(input())
    ax = 0.00000000
    ay = 0.00000000
    bx = 100.00000000
    by = 0.00000000
    
    print(str(ax) + " " + str(ay))
    koch(n, ax, ay, bx, by)
    print(str(bx)+ " " + str(by))

Solution (Python):
import sys
input = sys.stdin.readline
import math
a = math.sqrt(3) * 0.5
def koch(d, p1, p2):
    if d == 0:
        return
    else:
        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])*0.5-(t[1]-s[1])*a+s[0], (t[0]-s[0])*a+(t[1]-s[1])*0.5+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)

def main():
    n = int(input())
    p1 = [0, 0]
    p2 = [100, 0]
    print(p1[0], p1[1])
    koch(n, p1, p2)
    print(p2[0], p2[1])


if __name__ == '__main__': main()

Solution (Python):
import math

class Point:

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

def kock(n,p1,p2):
    if n==0:
        return
    
    
    sx=(2*p1.x+1*p2.x)/3
    sy=(2*p1.y+1*p2.y)/3
    s=Point(sx,sy)
    tx=(1*p1.x+2*p2.x)/3
    ty=(1*p1.y+2*p2.y)/3
    t=Point(tx,ty)
    ux=(tx-sx)*math.cos(math.pi/3)-(ty-sy)*math.sin(math.pi/3)+sx
    uy=(tx-sx)*math.sin(math.pi/3)+(ty-sy)*math.cos(math.pi/3)+sy
    u=Point(ux,uy)

    kock(n-1,p1,s)
    print('{:.8f}'.format(s.x),'{:.8f}'.format(s.y))
    kock(n-1,s,u)
    print('{:.8f}'.format(u.x),'{:.8f}'.format(u.y))
    kock(n-1,u,t)
    print('{:.8f}'.format(t.x),'{:.8f}'.format(t.y))
    kock(n-1,t,p2)

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


n=int(input())
print('{:.8f}'.format(p1.x),'{:.8f}'.format(p1.y))
kock(n,p1,p2)
print('{:.8f}'.format(p2.x),'{:.8f}'.format(p2.y))

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

def koch(n,a,b):
    if n==0:
        return
    th=math.pi*60.0/180.0
    s,t,u=[0,0],[0,0],[0,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(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,b)


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

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

Solution (Python):
import sys
import math

def print_point(point):

	print(f"{point[0]:.8f} {point[1]:.8f}")

def koch(n,p1,p2):

	if n == 0:
		return 0

	
	s = [0,0]
	t = [0,0]
	u = [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(math.radians(60)) - (t[1] - s[1]) * math.sin(math.radians(60)) + s[0]
	u[1] = (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_point(s)
	
	koch(n-1,s,u)
	print_point(u)

	koch(n-1,u,t)
	print_point(t)

	koch(n-1,t,p2)

def test():

	n = int(sys.stdin.readline())
	
	p1 = [0,0]
	p2 = [100,0]

	print_point(p1)
	koch(n,p1,p2)
	print_point(p2)

if __name__ == "__main__":
	test()

Solution (Python):
import math

n = int(input())

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

li = [[0, 0], [100, 0]]

for i in range(n):
    j = 0
    if n == 0:
        pass
    elif n == 1:
        li = [[0, 0], [100/3, 0], [50, 100/3*sin60], [100/3*2, 0], [100, 0]]
    else:
        for _ in range(4**i):
            sx = (li[j][0]*2 + li[j+1][0])/3
            sy = (li[j][1]*2 + li[j+1][1])/3
            tx = (li[j][0] + li[j+1][0]*2)/3
            ty = (li[j][1] + li[j+1][1]*2)/3
            ux = (tx-sx)*cos60 - (ty-sy)*sin60 + sx
            uy = (tx-sx)*sin60 + (ty-sy)*cos60 + sy
            li[j+1:0] = [[sx, sy], [ux, uy], [tx, ty]]
            j += 4

for i in range(len(li)):
    print('{:.8f} {:.8f}'.format(li[i][0], li[i][1]))

Solution (Python):
import math

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

    def __str__(self):
        return f"{self.x:.8f} {self.y:.8f}"


def koch(d, l, r):
    if d == 0:
        return

    s = Point()
    t = Point()
    u = Point()
    s.x = (2*l.x + 1*r.x) / (1 + 2)
    s.y = (2*l.y + 1*r.y) / (1 + 2)
    t.x = (1*l.x + 2*r.x) / (2 + 1)
    t.y = (1*l.y + 2*r.y) / (2 + 1)
    u.x = (t.x - s.x) * math.cos(math.radians(60)) - (t.y - s.y) * math.sin(math.radians(60)) + s.x
    u.y = (t.x - s.x) * math.sin(math.radians(60)) + (t.y - s.y) * math.cos(math.radians(60)) + s.y

    koch(d - 1, l, s)
    print(s)
    koch(d - 1, s, u)
    print(u)
    koch(d - 1, u, t)
    print(t)
    koch(d - 1, t, r)

n = int(input())
l, r = Point(), Point(100.0, 0.0)
print(l)
koch(n, l, r)
print(r)

Solution (Python):
import math

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

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

    s = Point()
    u = Point()
    t = Point()
    rad = math.radians(60)

    s.x = (2 * p1.x + 1 * p2.x) / 3
    s.y = (2 * p1.y + 1 * p2.y) / 3
    t.x = (1 * p1.x + 2 * p2.x) / 3
    t.y = (1 * p1.y + 2 * p2.y) / 3
    u.x = (t.x - s.x) * math.cos(rad) - (t.y - s.y) * math.sin(rad) + s.x
    u.y = (t.x - s.x) * math.sin(rad) + (t.y - s.y) * math.cos(rad) + s.y
    
    koch(d-1, p1, s)
    print(s.x, s.y)
    koch(d-1, s, u)
    print(u.x, u.y)
    koch(d-1, u, t)
    print(t.x, t.y)
    koch(d-1, t, p2)

def main():
    n = int(input())
    a = Point()
    b = Point()

    a.x = 0.0
    a.y = 0.0
    b.x = 100.0
    b.y = 0.0

    print(a.x, a.y)
    koch(n, a, b)
    print(b.x, b.y)
    
             
if __name__ == "__main__":
    main()

Solution (Python):
import math

def get_input():
    depth = int(input())
    return depth


def koch_curve(p1, p2):
    dp=[(p2[0]-p1[0])/3, (p2[1]-p1[1])/3]
    
    point3=[p1[0]+dp[0], p1[1] + dp[1]]
    point5=[p1[0]+dp[0]*2, p1[1] + dp[1]*2]

    rad60 = math.pi/3
    dp2 = [dp[0]*math.cos(rad60)-dp[1]*math.sin(rad60), 
           dp[0]*math.sin(rad60)+dp[1]*math.cos(rad60)]
    

    point4=[point3[0]+dp2[0], point3[1] + dp2[1]]

    return ([point3, point4, point5])



def rec_koch_curve(pl, depth, target):
    if (target <= depth) :
        return
    
    for i in range(len(pl)-1)[::-1]:
        tplist = koch_curve(pl[i] , pl[i+1])
        for p in tplist[::-1]:
            pl.insert(i+1, p)

    rec_koch_curve(pl, depth+1, target)

def print_curve(pl):
    for p in pl:
        print(p[0],p[1],sep=" ")

pl = [[0,0],[100,0]]
rec_koch_curve(pl, 0, get_input())
print_curve(pl)

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

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

def Koch(n,p1,p2):
    if n == 0:
        return
    else:
        s = Coordinate(2/3 * p1.x + 1/3 * p2.x, 2/3 * p1.y + 1/3 * p2.y)
        u = Coordinate(1/3 * p1.x + 2/3 * p2.x, 1/3 * p1.y + 2/3 * p2.y)
        t = Coordinate(1/2*(u.x-s.x) - math.sqrt(3)/2*(u.y-s.y) + s.x, math.sqrt(3)/2*(u.x-s.x) + 1/2*(u.y-s.y) + s.y)
        Koch(n-1,p1,s)
        print(str(s.x) +" "+str(s.y))
        Koch(n-1,s,t)
        print(str(t.x) +" "+str(t.y))
        Koch(n-1,t,u)
        print(str(u.x) +" "+str(u.y))
        Koch(n-1,u,p2)

p1 = Coordinate(0,0)
p2 = Coordinate(100,0)
print(str(p1.x) +" "+str(p1.y))
Koch(n,p1,p2)
print(str(p2.x) +" "+str(p2.y))

Solution (Python):
import math


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


def koch(n, p1, p2):
    if n == 0:
        return
    s, t, u = [Point() for _ in range(3)]
    s.x = (2 * p1.x + p2.x) / 3
    s.y = (2 * p1.y + p2.y) / 3
    t.x = (p1.x + 2 * p2.x) / 3
    t.y = (p1.y + 2 * p2.y) / 3
    a = math.radians(60)
    u.x = (t.x - s.x) * math.cos(a) - (t.y - s.y) * math.sin(a) + s.x
    u.y = (t.x - s.x) * math.sin(a) + (t.y - s.y) * math.cos(a) + s.y

    koch(n - 1, p1, 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, p2)


p1 = Point(0, 0)
p2 = Point(100, 0)
n = int(input())
print(p1.x, p1.y)
koch(n, p1, p2)
print(p2.x, p2.y)

Solution (Python):
import math
con=math.sqrt(3)/2

def gohho(da):
    ans=[]
    n=len(da)
    for i in range(n-1):
        ans.append(da[i])
        ans.append([(da[i][0]*2+da[i+1][0])/3,(da[i][1]*2+da[i+1][1])/3])
        ans.append([(da[i][0]*2+da[i+1][0])/3+(da[i+1][0]-da[i][0])*0.5/3-(da[i+1][1]-da[i][1])*con/3,(da[i][1]*2+da[i+1][1])/3+(da[i+1][0]-da[i][0])*con/3+(da[i+1][1]-da[i][1])*0.5/3])
        ans.append([(da[i][0]+da[i+1][0]*2)/3,(da[i][1]+da[i+1][1]*2)/3])
    ans.append(da[-1])
    return ans

n=int(input())
da=[[0,0],[100,0]]
for i in range(n):
    da=gohho(da)
for i in da:
    print(i[0],i[1])

Solution (Python):
import math

c60 = math.cos(math.radians(60))
s60 = math.sin(math.radians(60))

def koch(d, p1, p2):
    if d == 0:
        return
    
    sx = (p2[0] + 2 * p1[0]) / 3
    sy = (p2[1] + 2 * p1[1]) / 3
    tx = (p2[0] * 2 + p1[0]) / 3
    ty = (p2[1] * 2 + p1[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:.5f} {1:.5f}".format(sx, sy))
 
    koch(d-1, (sx, sy), (ux, uy))
    print("{0:.5f} {1:.5f}".format(ux, uy))
 
    koch(d-1, (ux, uy), (tx, ty))
    print("{0:.5f} {1:.5f}".format(tx, ty))
    
    koch(d-1, (tx, ty), p2)

n = int(input())

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

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

def koch_curve(p1_x,p1_y,p2_x,p2_y,c):
	s_x = (p2_x + 2*p1_x) / 3
	s_y = (p2_y + 2*p1_y) / 3
	t_x = (2*p2_x + p1_x) / 3
	t_y = (2*p2_y + p1_y) / 3
	u_x = (math.cos(math.pi/3) * ( t_x - s_x ) - math.sin(math.pi/3) * ( t_y - s_y)) + s_x
	u_y = (math.sin(math.pi/3) * ( t_x - s_x ) + math.cos(math.pi/3) * ( t_y - s_y)) + s_y
	if c > 1:
		koch_curve(p1_x,p1_y,s_x,s_y,c-1)
		koch_curve(s_x,s_y,u_x,u_y,c-1)
		koch_curve(u_x,u_y,t_x,t_y,c-1)
		koch_curve(t_x,t_y,p2_x,p2_y,c-1)
	else:
		print("%.8f %.8f" % (p1_x,p1_y))
		print("%.8f %.8f" % (s_x, s_y))
		print("%.8f %.8f" % (u_x, u_y))
		print("%.8f %.8f" % (t_x, t_y))

if __name__ == '__main__':
	n = int(input())
	if n == 0:
		print("%.8f %.8f" % (0,0))
		print("%.8f %.8f" % (100,0))
	else:
		koch_curve(0,0,100,0,n)
		print("%.8f %.8f" % (100,0))

Solution (Python):
from functools import reduce
import math

orientation = math.cos(math.pi/3) + 1j * math.sin(math.pi/3)


def main():
    n = int(input())
    results = [(0.0, 0.0), (100.0, 0.0)]
    results = koch_curve(results, 0, n)
    for r in results:
        print(r[0], r[1])


def f(a, b):
    c = ((2*a[0]+b[0])/3, (2*a[1]+b[1])/3)
    d = ((a[0]+2*b[0])/3, (a[1]+2*b[1])/3)
    vec = d[0] + d[1]*1j - (c[0] + 1j*c[1])
    e = vec * orientation
    e += (c[0] + 1j*c[1])
    e = (e.real, e.imag)
    return [a, c, e, d]


def koch_curve(lst, i, maximum):
    if i == maximum:
        return lst
    else:
        results = []
        l = len(lst)
        for j in range(l-1):
            results += f(lst[j], lst[j+1])
        results += [lst[j+1]]
        return koch_curve(results, i+1, maximum)


if __name__ == '__main__':
    main()

Solution (Python):

p1 = [0,0]
p2 = [100,0]
R = [[0.5,-1.7320508/2],[1.7320508/2,0.5]]

def dot(A,b):
    vs = [0,0]
    for i in range(2):
        for j in range(2):
            vs[i] += A[i][j]*b[j]
    return vs

def diff(p1,p2):
    return [(p1[0]-p2[0])/3.0,(p1[1]-p2[1])/3.0]

def sumV(p1,p2):
    return [p1[0]+p2[0],p1[1]+p2[1]]

def new_koch(p1,p2):
    p = diff(p2,p1)
    p_new1 = sumV(p1,p)
    p_new2 = sumV(p_new1,dot(R,p))
    p_new3 = sumV(p1,sumV(p,p))
    return [p1,p_new1,p_new2,p_new3]

n = int(input())
ps = [p1,p2]
for i in range(n):    
    X = len(ps)
    ps_new = []
    for i in range(X-1):
        ps_new.extend(new_koch(ps[i],ps[i+1]))
    ps_new += [ps[-1]]
    ps = [p for p in ps_new]

for p in ps:
    print(*p)

Solution (Python):
import math


def rot60_on_complex_plane(start: complex, end: complex) -> complex:
    v = end - start
    arg = 1 / 2 + complex(0, (math.sqrt(3) / 2))
    return v * arg + start


def print_real_coordinate(z: complex) -> None:
    x = z.real
    y = z.imag
    print(f"{x:.8f} {y:.8f}")


def create_koch_points(p1: complex, p2: complex, n: int) -> None:
    if n == 0:
        return

    
    s = (p2 - p1) * (1 / 3) + p1
    t = (p2 - p1) * (2 / 3) + p1
    u = rot60_on_complex_plane(s, t)

    
    create_koch_points(p1, s, n - 1)
    print_real_coordinate(s)
    create_koch_points(s, u, n - 1)
    print_real_coordinate(u)
    create_koch_points(u, t, n - 1)
    print_real_coordinate(t)
    create_koch_points(t, p2, n - 1)


if __name__ == "__main__":
    n = int(input())
    start_point = (0 + 0j)
    end_point = (100 + 0j)

    print_real_coordinate(start_point)
    create_koch_points(start_point, end_point, n)
    print_real_coordinate(end_point)

Solution (Python):
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

def kock(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
    ux = (tx - sx)*math.cos(math.pi/3) - (ty - sy)*math.sin(math.pi/3) + sx
    uy = (tx - sx)*math.sin(math.pi/3) + (ty - sy)*math.cos(math.pi/3) + sy

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


n = int(input())
p1x = 0; p1y = 0; p2x = 100; p2y = 0
print("%f %f"%(p1x,p1y))
kock(n,p1x,p1y,p2x,p2y)
print("%f %f"%(p2x,p2y))

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):
def Rot(vec):
    new=[]
    new+=[vec[0]/2-vec[1]*3**(1/2)/2]
    new+=[vec[0]*3**(1/2)/2+vec[1]/2]
    return(new)

def Add(L):
    dist=[(L[1][0]-L[0][0])/3,(L[1][1]-L[0][1])/3]
    vec1=Rot(dist)
    p1=[2/3*L[0][0]+1/3*L[1][0],2/3*L[0][1]+1/3*L[1][1]]
    p2=[p1[0]+vec1[0],p1[1]+vec1[1]]
    p3=[2/3*L[1][0]+1/3*L[0][0],2/3*L[1][1]+1/3*L[0][1]]
    return([L[0],p1,p2,p3,L[1]])

def Koch(L,n):
    l=len(L)
    if n==0:
        Out=L
    elif n==1:
        if l==2:
            Out=Add(L)
        else:
            L1=L[0:l//2+1]
            L2=L[l//2:l]

            Out=Koch(L1,n)[:-1]+Koch(L2,n)
    else:
        Out=(Koch(Koch(L,n-1),1))

    return(Out)

n=int(input())
L=Koch([[0,0],[100,0]],n)
l=len(L)
for i in range(l):
    print(L[i][0],L[i][1])

Solution (Python):
import math


def solve(depth, p1, p2):
    if depth == 0:
        return
    else:
        px = (p2[0] - p1[0]) / 3
        py = (p2[1] - p1[1]) / 3
        s = [p1[0] + px, p1[1] + py]
        t = [p1[0] + 2 * px, p1[1] + 2 * py]
        u = [(t[0] - s[0]) * math.cos(math.pi/3) -
             (t[1] - s[1]) * math.sin(math.pi/3) + s[0],
             (t[0] - s[0]) * math.sin(math.pi/3) +
             (t[1] - s[1]) * math.cos(math.pi/3) + s[1]]
        solve(depth-1, p1, s)
        print(*s)
        solve(depth-1, s, u)
        print(*u)
        solve(depth-1, u, t)
        print(*t)
        solve(depth-1, t, p2)


def main():
    n = int(input())
    print("%f %f" % (0, 0))
    solve(n, [0, 0], [100, 0])
    print("%f %f" % (100, 0))


if __name__ == '__main__':
    main()

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):
from decimal import Decimal
from math import cos, radians, sin



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

    def output(self):
        print("{:.6f} {:.6f}".format(self.x, self.y))

    def calc_koch_apex(self, point):
        s_x = Decimal(2) / Decimal(3) * self.x + Decimal(1) / Decimal(3) * point.x
        s_y = Decimal(2) / Decimal(3) * self.y + Decimal(1) / Decimal(3) * point.y
        s = Point(s_x, s_y)

        t_x = Decimal(1) / Decimal(3) * self.x + Decimal(2) / Decimal(3) * point.x
        t_y = Decimal(1) / Decimal(3) * self.y + Decimal(2) / Decimal(3) * point.y
        t = Point(t_x, t_y)

        u_x = (t.x - s.x) * Decimal(cos(radians(60))) - \
              (t.y - s.y) * Decimal(sin(radians(60))) + s.x
        u_y = (t.x - s.x) * Decimal(sin(radians(60))) + \
              (t.y - s.y) * Decimal(cos(radians(60))) + s.y
        u = Point(u_x, u_y)

        return s, u, t


def kock(n, point1, point2):
    if n == 0:
        return


    s, u, t = point1.calc_koch_apex(point2)
    
    kock(n-1, point1, s)

    s.output()

    kock(n-1, s, u)

    u.output()

    kock(n-1, u, t)

    t.output()

    kock(n-1, t, point2)




n = int(input())

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


p1.output()

kock(n, p1, p2)

p2.output()