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


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

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


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

Solution (Python):

from math import sin, cos, tan, pi

n = int(input())

def koch(n, a, b):
	if n == 0:
		return
	s = [0, 0]
	t = [0, 0]
	u = [0, 0]
	th = pi * 60 / 180

	s[0] = (2 * a[0] + 1 * b[0]) / 3
	s[1] = (2 * a[1] + 1 * b[1]) / 3
	t[0] = (1 * a[0] + 2 * b[0]) / 3
	t[1] = (1 * a[1] + 2 * b[1]) / 3
	u[0] = (t[0] - s[0]) * cos(th) - (t[1] - s[1]) * sin(th) + s[0]
	u[1] = (t[0] - s[0]) * sin(th) + (t[1] - s[1]) * 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, 0.0]
b = [100.0, 0.0]
print(a[0], a[1])

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

Solution (Python):
import math

def koch(p1, p2, n):
    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(p1, s, n-1)
    print('{:8f} {:8f}'.format(s[0], s[1]))
    koch(s, u, n-1)
    print('{:8f} {:8f}'.format(u[0], u[1]))
    koch(u, t, n-1)
    print('{:8f} {:8f}'.format(t[0], t[1]))
    koch(t, p2, n-1)


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

    n = int(input())

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

    print('{:8f} {:8f}'.format(a[0], a[1]))
    koch(a, b, n)
    print('{:8f} {:8f}'.format(b[0], b[1]))

Solution (Python):
import math

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

    def __add__(self,a):
        return self.__class__(self.x+a.x,self.y+a.y)

    def __sub__(self,a):
        return self.__class__(self.x-a.x,self.y-a.y)

    def __mul__(self,d):
        return self.__class__(self.x*d,self.y*d)

    def __truediv__(self,d):
        return self.__class__(self.x/d,self.y/d)

    def __str__(self):
        return '%.10f %.10f'%(self.x,self.y)

    def abs(self):
        return (self.x*self.x+self.y*self.y)**(1.0/2.0)

    def rotate(self,d):
        r = math.pi*d/180.0
        return self.__class__( self.x*math.cos(r)-self.y*math.sin(r),
                               self.x*math.sin(r)+self.y*math.cos(r))

def func(p1,p2,n):

    if n==0:return

    v = (p2-p1)
    a = p1+v/3.0
    c = p1+v*2.0/3.0
    b = a+(c-a).rotate(60.0)

    func(p1,a,n-1)
    print (a)
    func(a,b,n-1)
    print (b)
    func(b,c,n-1)
    print (c)
    func(c,p2,n-1)

def main():
    n = int(input())
    a = Point(0.0,0.0)
    b = Point(100.0,0.0)
    print (a)
    func(a,b,n)
    print (b)

if __name__ == '__main__':
    main()

Solution (Python):
import math

sin = math.sin(math.pi/3)
cos = math.cos(math.pi/3)

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

def koch(d, p1, p2):
    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])
    u = ((t[0] - s[0]) * cos - (t[1] - s[1]) * sin + s[0], (t[0] - s[0]) * sin + (t[1] - s[1]) * cos + 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):
n = int(input())
p1, p2 = (0, 0), (100, 0)
ans_ls = [p1, p2]

def koch(d, p1, p2):
	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, -(3**(1/2))/2], [(3**(1/2))/2, 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):


import math

class Point():

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

    def __repr__(self):
        return str(self.x) + " " + str(self.y)


def Koch(p1, p2, n):
    if n == 0:
        print(p1)
    else:
        s = Point(p1.x * 2 / 3 + p2.x * 1 / 3, p1.y * 2 / 3 + p2.y * 1 / 3)
        u = Point(p1.x / 2 + p2.x / 2 + p1.y * r3 / 6 - p2.y * r3 / 6, p1.y / 2 + p2.y / 2 + p2.x * r3 / 6 - p1.x * r3 / 6)
        t = Point(p1.x * 1 / 3 + p2.x * 2 / 3, p1.y * 1 / 3 + p2.y * 2 / 3)
        Koch(p1, s, n - 1)
        Koch(s, u, n - 1)
        Koch(u, t, n - 1)
        Koch(t, p2, n - 1)


r3 = math.sqrt(3)
start = Point(0, 0)
goal = Point(100, 0)
n = int(input())
Koch(start, goal, n)
print(goal)

Solution (Python):
from typing import List
import math

def koch_curve(n: int, p1: List[float], p2: List[float]):
    if n == 0:
        return
    p1x, p1y = p1
    p2x, p2y = p2
    s = [(r - l) / 3 + l for (l, r) in zip(p1, p2)]
    t = [(r - l) * 2 / 3 + l for (l, r) in zip(p1, p2)]
    sx, sy = s
    tx, ty = t
    ux = (tx - sx) * math.cos(math.radians(60)) - (ty - sy) * math.sin(math.radians(60)) + sx
    uy = (tx - sx) * math.sin(math.radians(60)) + (ty - sy) * math.cos(math.radians(60)) + sy
    u = [ux, uy]
    n -= 1
    koch_curve(n, p1, s)
    print(*s)
    koch_curve(n, s, u)
    print(*u)
    koch_curve(n, u, t)
    print(*t)
    koch_curve(n, t, p2)

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

Solution (Python):
def koch(d,p0,p1):
    
    if d == n:
        return
    
    
    s=[(2*p0[0]+p1[0])/3,(2*p0[1]+p1[1])/3]
    t=[(2*p1[0]+p0[0])/3,(2*p1[1]+p0[1])/3]
    
    
    u=[(p0[0]+p1[0])/2-(p1[1]-p0[1])*(3**(1/2)/6),(p1[1]+p0[1])/2+(p1[0]-p0[0])*(3**(1/2)/6)]
    
    koch(d+1,p0,s)
    print(*s)
    
    koch(d+1,s,u)
    print(*u)
    
    koch(d+1,u,t)
    print(*t)
    
    koch(d+1,t,p1)
    
p0=[0,0]
p1=[100,0]


n=int(input())

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

Solution (Python):
import math


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

    def print(self):
        print(self.x, self.y)

    def __add__(self, o):
        return Vector(self.x + o.x, self.y + o.y)

    def __sub__(self, o):
        return Vector(self.x - o.x, self.y - o.y)

    def __mul__(self, o):
        return Vector(self.x * o, self.y * o)

    def __truediv__(self, o):
        return Vector(self.x / o, self.y / o)

    def rot(self, deg):
        rad = math.radians(deg)
        x = self.x * math.cos(rad) - self.y * math.sin(rad)
        y = self.x * math.sin(rad) + self.y * math.cos(rad)
        return Vector(x, y)


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

    s = a + (b-a)/3
    u = s + (s-a).rot(60)
    t = a + (b-a)*2/3

    koch(d-1, a, s)
    s.print()
    koch(d-1, s, u)
    u.print()
    koch(d-1, u, t)
    t.print()
    koch(d-1, t, b)


N = int(input())

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


a.print()
koch(N, a, b)
b.print()

Solution (Python):

import sys,collections
n = int(sys.stdin.readline())

def koch(p1,p2,n):
  if n == 0:
    return [p1,p2]
  ret = []
  
  s = [(p2[0]+2*p1[0])/3.0,(p2[1]+2*p1[1])/3.0]
  
  t = [(2*p2[0]+p1[0])/3.0,(2*p2[1]+p1[1])/3.0]
  u = [(t[0]+s[0]+1.73205*(s[1]-t[1]))/2.0,(1.73205*(t[0]-s[0])+t[1]+s[1])/2.0]
  if n == 1:
    return [p1,s,u,t,p2]
  for l in [[p1,s],[s,u],[u,t],[t,p2]]:
    ret += koch(l[0],l[1],n-1)[:-1]
  ret += [p2]
  return ret






print("\n".join([str(p1)+" "+str(p2) for p1,p2 in koch([0.0,0.0],[100.0,0.0],n)]))

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 math import cos, sin, pi

n = int(input())

p1 = (0, 0)
p2 = (100, 0)
theta = pi/3


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

    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(theta) - (ty - sy) * sin(theta) + sx
    uy = (tx - sx) * sin(theta) + (ty - sy) * cos(theta) + sy

    koch(d-1, p1, (sx, sy))
    print("{} {}".format(sx, sy))
    koch(d-1, (sx, sy), (ux, uy))
    print("{} {}".format(ux, uy))
    koch(d-1, (ux, uy), (tx, ty))
    print("{} {}".format(tx, ty))
    koch(d-1, (tx, ty), p2)


print("{} {}".format(p1[0], p1[1]))
koch(n, p1, p2)
print("{} {}".format(p2[0], p2[1]))

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

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

n =  int(input())

def koch(d, p, q):
    if d == 0:
        return
    s=[0,0]
    t=[0,0]
    u=[0,0]
    s[0] = (2 * p[0] + q[0]) / 3
    s[1] = (2 * p[1] + q[1]) / 3
    t[0] = (p[0] + 2 * q[0]) / 3
    t[1] = (p[1] + 2 * q[1]) / 3
    u[0] = (t[0] - s[0]) * cos60 - (t[1] - s[1]) * sin60 + s[0]
    u[1] = (t[0] - s[0]) * sin60 + (t[1] - s[1]) * cos60 + s[1]
    
    koch(d-1, p, 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, q)

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 coordinate:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    

def koch(n, p1, p2):
    if n == 0:
        return str(p2.x) + " " + str(p2.y)
    
    else:
        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)
        u = coordinate((t.x-s.x)/2-(t.y-s.y)/2*math.sqrt(3)+s.x, (t.x-s.x)/2*math.sqrt(3)+(t.y-s.y)/2+s.y)
        print(koch(n-1, p1, s))
        print(koch(n-1, s, u))
        print(koch(n-1, u, t))
        return(koch(n-1, t, p2))


q1 = coordinate(0.00000000, 0.00000000)
q2 = coordinate(100.00000000, 0.00000000)

print(str(q1.x) + " " + str(q1.y))
print(koch(int(input()), q1, q2))

Solution (Python):
import math


def split3(a, b):
    s = (a[0] * (2 / 3) + b[0] * (1 / 3), a[1] * (2 / 3) + b[1] * (1 / 3))
    t = (a[0] * (1 / 3) + b[0] * (2 / 3), a[1] * (1 / 3) + b[1] * (2 / 3))
    return s, t


def rotate60(s, t):
    th = math.pi / 3
    u0 = s[0] + math.cos(th) * (t[0] - s[0]) - math.sin(th) * (t[1] - s[1])
    u1 = s[1] + math.sin(th) * (t[0] - s[0]) + math.cos(th) * (t[1] - s[1])
    return (u0, u1)


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

for i in range(n):
    L = len(lst)
    new_lst = []
    for l in range(L - 1):
        left = lst[l]
        right = lst[l + 1]
        new_lst.append(left)
        s, t = split3(left, right)
        u = rotate60(s, t)
        new_lst.append(s)
        new_lst.append(u)
        new_lst.append(t)
    new_lst.append(right)
    lst = new_lst
for p in lst:
    print(*p)

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
INFTY=100000000

n=int(input())

def kock(p1,p2,n):
    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=[(t[0]-s[0])/2-(t[1]-s[1])/2*math.sqrt(3)+s[0], (t[0]-s[0])/2*math.sqrt(3)+(t[1]-s[1])/2+s[1]]
    if n==0:
        print("%.8f %.8f"%(p1[0],p1[1]))
    else:
        kock(p1,s,n-1)
        kock(s,u,n-1)
        kock(u,t,n-1)
        kock(t,p2,n-1)

start=[0.0,0.0]
end=[100.0, 0.0]
if n==0:
    print("%.8f %.8f"%(start[0],start[1]))
    print("%.8f %.8f"%(end[0],end[1]))
else:
    kock(start,end,n)
    print("%.8f %.8f"%(end[0],end[1]))

Solution (Python):
import math
N = int(input())
X = [0., 0.]
Y = [100., 0.]

rad = math.pi / 2 * 2 /3

def rot(rad, pos):
    return [math.cos(rad)*pos[0] - math.sin(rad)*pos[1], math.sin(rad)*pos[0] + math.cos(rad)*pos[1]]


def coh(left, right, cnt):
    
    if cnt == 0:
        return
    else:
        s = [(right[0] - left[0]) / 3 + left[0], (right[1] - left[1]) / 3 + left[1]]
        t = [(right[0] - left[0]) * 2 / 3 + left[0], (right[1] - left[1]) * 2 / 3 + left[1]]
        ux, uy = rot(rad, [t[0] - s[0], t[1] - s[1]])
        u = [ux + s[0], uy + s[1]]

        coh(left, s, cnt-1)
        print(*s)
        coh(s, u, cnt-1)
        print(*u)
        coh(u, t, cnt-1)
        print(*t)
        coh(t, right, cnt-1)

print(*X)
coh(X, Y, N)
print(*Y)

Solution (Python):
def inner_prod(v0, v1):
    ans = 0
    for x0, x1 in zip(v0, v1):
        ans += x0 * x1
    return ans


def vector_add(v0, v1):
    return [x0 + x1 for x0, x1 in zip(v0, v1)]


def vector_mul(vector, scaler):
    return [scaler * x for x in vector]


def matrix_mul(matrix, vector):
    ans = []
    for row in matrix:
        ans.append(inner_prod(row, vector))
    return ans


def koch(p0, p1, max_depth, depth=0):
    from math import sin, cos, pi

    if depth == max_depth:
        return []
    R = [[cos(pi / 3), -sin(pi / 3)], [sin(pi / 3), cos(pi / 3)]]
    p2 = vector_add(vector_mul(p0, 2 / 3), vector_mul(p1, 1 / 3))
    p3 = vector_add(vector_mul(p0, 1 / 3), vector_mul(p1, 2 / 3))
    p4 = vector_add(p2, matrix_mul(R, vector_add(p3, vector_mul(p2, -1))))
    return [
        koch(p0, p2, max_depth, depth + 1),
        p2,
        koch(p2, p4, max_depth, depth + 1),
        p4,
        koch(p4, p3, max_depth, depth + 1),
        p3,
        koch(p3, p1, max_depth, depth + 1),
    ]


def dfs_print(array):
    if not array:
        return
    if isinstance(array[0], int) or isinstance(array[0], float):
        print(*array)
    else:
        for child in array:
            dfs_print(child)


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

Solution (Python):
import math

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

def knoc(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)
    ux = (t[0]-s[0])*cos60-(t[1]-s[1])*sin60+s[0]
    uy = (t[0]-s[0])*sin60+(t[1]-s[1])*cos60+s[1]
    u = (ux, uy)
    
    knoc(n-1, l, s)
    print(s[0],s[1])
    knoc(n-1, s, u)
    print(u[0],u[1])
    knoc(n-1, u, t)
    print(t[0],t[1])
    knoc(n-1, t, r)
    
n = int(input())

start = (0,0)
end = (100,0)

print(start[0],start[1])
knoc(n, start, end)
print(end[0],end[1])

Solution (Python):
import math

def koch(p1, p2, dp):

    if dp == 0:
        return
    
    sX = (p2[0] - p1[0]) / 3 + p1[0]
    sY = (p2[1] - p1[1]) / 3 + p1[1]
    s = (sX, sY)

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

    uX = (tX - sX) * math.cos(math.radians(60)) - (tY - sY) * math.sin(math.radians(60)) + sX
    uY = (tX - sX) * math.sin(math.radians(60)) + (tY - sY) * math.cos(math.radians(60)) + sY
    u = (uX, uY)

    koch(p1, s, dp - 1)
    myPrint(s)
    koch(s, u, dp - 1)
    myPrint(u)
    koch(u, t, dp - 1)
    myPrint(t)
    koch(t, p2, dp - 1)

    
def myPrint(val):
    print("{:.8f} {:.8f}".format(val[0], val[1]))
    

n = int(input())

p1 = (0.0, 0.0)
p2 = (100.0, 0.0)

myPrint(p1)
koch(p1, p2, n)
myPrint(p2)

Solution (Python):
import math

def curve(inp):
    ret = []
    n = len(inp)
    cos60 = math.cos(math.radians(60))
    sin60 = math.sin(math.radians(60))
    for i in range(n - 1):
        p1x, p1y = inp[i]
        p2x, p2y = inp[i+1]
        
        diffx = (p2x - p1x) / 3
        diffy = (p2y - p1y) / 3
        sx, sy = p1x + diffx, p1y + diffy
        ux = sx + diffx * cos60 - diffy * sin60
        uy = sy + diffx * sin60 + diffy * cos60
        tx, ty = p2x - diffx, p2y - diffy
        
        ret.extend([(p1x, p1y), (sx, sy), (ux, uy), (tx, ty)])
    ret.append(inp[-1])
        
    return ret
      
      
if __name__=="__main__":
    inp = [(0.0, 0.0), (100.0, 0.0)]
    N = int(input())
    for i in range(N):
        inp = curve(inp)
    for i in inp:
      print(*i)

Solution (Python):
import sys
import math
import copy
from typing import Tuple, List, Union
input = sys.stdin.readline

sin60 = math.sqrt(3) / 2
cos60 = 1/ 2

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


def koch(n: int, p1, p2):
    if n == 0:
        return
    s = Position((2 * p1.x + p2.x) / 3, (2 * p1.y + p2.y) / 3)
    t = Position((p1.x + 2 * p2.x) / 3, (p1.y +  2 * p2.y) / 3)
    u = Position((t.x - s.x) * cos60 - (t.y - s.y) * sin60 + s.x,
                 (t.x - s.x) * sin60 + (t.y - s.y) * cos60 + s.y)
    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)



def main():
    n = int(input())
    p1 = Position(0.0, 0.0)
    p2 = Position(100.0, 0.0)
    print(p1)
    koch(n, p1, p2)
    print(p2)

if __name__ == '__main__':
    main()

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


def solve(p1, p2):
    s_x = p1.x + (p2.x - p1.x) * (1/3)
    s_y = p1.y + (p2.y - p1.y) * (1/3)
    t_x = p1.x + (p2.x - p1.x) * (2/3)
    t_y = p1.y + (p2.y - p1.y) * (2/3)
    u_x = (p2.x + p1.x) * (1/2) + (p1.y - p2.y) * (1/6) * pow(3, 1/2)
    u_y = (p2.y + p1.y) * (1/2) + (p2.x - p1.x) * (1/6) * pow(3, 1/2)
    s = Point(s_x, s_y)
    t = Point(t_x, t_y)
    u = Point(u_x, u_y)
    return [s, u, t]


if __name__ == "__main__":
    n = int(input())
    P = [Point(0, 0), Point(100, 0)]
    for i in range(n):
        TMP = []
        for j in range(len(P) - 1):
            TMP.append(P[j])
            TMP += solve(P[j], P[j+1])
        TMP.append(P[-1])
        P = TMP

    for p in P:
        print('{} {}'.format(p.x, p.y))

Solution (Python):
from math import sqrt


def func(N, p1, p2):
    if N == 0:
        return 0
    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)
    x = (t[0]-s[0])/2-sqrt(3)*(t[1]-s[1])/2+s[0]
    y = sqrt(3)*(t[0]-s[0])/2+(t[1]-s[1])/2+s[1]
    u = (x, y)
    func(N-1, p1, s)
    print(*s)
    func(N-1, s, u)
    print(*u)
    func(N-1, u, t)
    print(*t)
    func(N-1, t, p2)


N = int(input())
print(*(0.0, 0.0))
func(N, (0.0, 0.0), (100.0, 0.0))
print(*(100.0, 0.0))

Solution (Python):
import math

def coh(n, p1, p2, pt_list, m):
    if n>m:
        return 
    x1, y1 = p1
    x2, y2 = p2
    
    nx, ny = -(y2-y1), x2-x1

    xs, ys = x1 + (x2-x1)/3, y1 + (y2-y1)/3
    xu, yu = (x1+x2)/2 + nx*math.sqrt(3)/2/3 , (y1+y2)/2 + ny*math.sqrt(3)/2/3  
    xt, yt = x1 + (x2-x1)*2/3, y1 + (y2-y1)*2/3
    
    ps = xs, ys
    pu = xu, yu
    pt = xt, yt
    
    coh(n+1, p1, ps, pt_list, m)
    pt_list += [ps]
    coh(n+1, ps, pu, pt_list, m)
    pt_list += [pu]
    coh(n+1, pu, pt, pt_list, m)
    pt_list += [pt]
    coh(n+1, pt, p2, pt_list, m)

m = int(input())
pt_list = [(0,0)]
coh(1, (0,0), (100,0), pt_list, m)
pt_list += [(100,0)]
for xy in pt_list:
    print('%.9f %.9f'%(xy[0], xy[1]))

Solution (Python):
import math

def koch_kurve(n, p1=[0, 0], p2=[100, 0]):
  if n == 0: return

  s, t, u = make_edge_list(p1, p2)

  koch_kurve(n-1, p1, s)
  
  
  print(" ".join([ str(i) for i in s ]))
  koch_kurve(n-1, s, u)
  print(" ".join([ str(i) for i in u ]))
  koch_kurve(n-1, u, t)
  print(" ".join([ str(i) for i in t ]))
  koch_kurve(n-1, t, p2)


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

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

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

  return s, t, u

n = int(input())
print("0 0")
koch_kurve(n)
print("100 0")

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

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

def koch(p1, p2, count):

    if count == 0:
        return

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

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

    p4 = [ (p5[0]-p3[0])*cos(pi/3) - (p5[1]-p3[1])*sin(pi/3) + p3[0], \
        (p5[0]-p3[0])*sin(pi/3) + (p5[1]-p3[1])*cos(pi/3) + p3[1]] 

    koch(p1, p3, count - 1)
    print(*p3) 
    koch(p3, p4, count - 1)
    print(*p4) 
    koch(p4, p5, count - 1)
    print(*p5) 
    koch(p5, p2, count - 1)

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

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, (2*p1[1]+p2[1])/3]
    t = [(p1[0]+2*p2[0])/3, (p1[1]+2*p2[1])/3]
    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

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

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

    else:
        s = Point()
        t = Point()
        u = Point()

        s.x = (2*p1.x + 1*p2.x)/3.0
        s.y = (2*p1.y + 1*p2.y)/3.0

        t.x = (1*p1.x + 2*p2.x)/3.0
        t.y = (1*p1.y + 2*p2.y)/3.0

        u.x = s.x + math.cos(math.radians(60)) * (t.x - s.x) - math.sin(math.radians(60)) * (t.y - s.y)
        u.y = s.y + math.sin(math.radians(60)) * (t.x - s.x) + math.cos(math.radians(60)) * (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)

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

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

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

main()

Solution (Python):
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect
import sys
import random
import time
inf = 10**9


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)
    u = Coordinate(
        (t.x - s.x) * math.cos(math.pi / 3) -
        (t.y - s.y) * math.sin(math.pi / 3) + s.x,
        (t.x - s.x) * math.sin(math.pi / 3) +
        (t.y - s.y) * math.cos(math.pi / 3) + s.y
    )

    kock(n - 1, p1, s)
    print(s.x, s.y)
    kock(n - 1, s, u)
    print(u.x, u.y)
    kock(n - 1, u, t)
    print(t.x, t.y)
    kock(n - 1, t, p2)


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

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

    print(p1.x, p1.y)
    kock(n, p1, p2)
    print(p2.x, p2.y)


if __name__ == '__main__':
    main()

Solution (Python):

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

def kock(n, p1, p2):
    if n == 0: return
    
    s = [0, 0]
    t = [0, 0]
    u = [0, 0]
    sin60 = (3 ** 0.5) / 2
    cos60 = (1 ** 0.5) / 2

    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]) * cos60) - ((t[1] - s[1]) * sin60)) + s[0]
    u[1] = (((t[0] - s[0]) * sin60) + ((t[1] - s[1]) * cos60)) + s[1] 

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

print(f"{p1[0]:.8f} {p1[1]:.8f}")
kock(input_n, p1, p2)
print(f"{p2[0]:.8f} {p2[1]:.8f}")

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

def koch(n,x1,y1,x2,y2):
    if n == 0:
        print(x1,y1)
    else:
        a = 3**(1/2)/2
        p1 = koch(n-1,x1,y1,(2*x1+x2)/3,(2*y1+y2)/3)
        if abs(y1 - y2) <= 10**(-4):
            s = koch(n-1,(2*x1+x2)/3,(2*y1+y2)/3,(x1+x2)/2,y1+(x2-x1)*a/3)
            u = koch(n-1,(x1+x2)/2,y1+(x2-x1)*a/3,(x1+2*x2)/3,(y1+2*y2)/3)
        else:
            if x1 < x2 and y1 < y2:
                s = koch(n-1,(2*x1+x2)/3,(2*y1+y2)/3,x1,(y1+2*y2)/3)
                u = koch(n-1,x1,(y1+2*y2)/3,(x1+2*x2)/3,(y1+2*y2)/3)
            elif x1 < x2 and y1 > y2:
                s = koch(n-1,(2*x1+x2)/3,(2*y1+y2)/3,x2,(2*y1+y2)/3)
                u = koch(n-1,x2,(2*y1+y2)/3,(x1+2*x2)/3,(y1+2*y2)/3)
            elif x1 > x2 and y1 < y2:
                s = koch(n-1,(2*x1+x2)/3,(2*y1+y2)/3,x2,(2*y1+y2)/3)
                u = koch(n-1,x2,(2*y1+y2)/3,(x1+2*x2)/3,(y1+2*y2)/3)
            else:
                s = koch(n-1,(2*x1+x2)/3,(2*y1+y2)/3,x1,(y1+2*y2)/3)
                u = koch(n-1,x1,(y1+2*y2)/3,(x1+2*x2)/3,(y1+2*y2)/3)
        t = koch(n-1,(x1+2*x2)/3,(y1+2*y2)/3,x2,y2)
        return p1,s,u,t

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

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):
import math 
c = math.cos(math.radians(60))
s = math.sin(math.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] + p2[0] * 2) / 3
    ty = (p1[1] + p2[1] * 2) / 3

    dx = tx - sx
    dy = ty - sy

    ux = dx * c - dy * s + sx
    uy = dx * s + dy * c + 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())
print("{0:.8f} {1:.8f}".format(0,0))
koch(n,(0,0),(100,0))
print("{0:.8f} {1:.8f}".format(100,0))

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


class Point:

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

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


def kock(n, p1: Point, p2: Point):
    if n == 0:
        return
    s = Point(
        x=(2*p1.x + p2.x)/3,
        y=(2*p1.y + p2.y)/3
    )
    t = Point(
        x=(p1.x + 2*p2.x)/3,
        y=(p1.y + 2*p2.y)/3
    )
    u = Point(
        x=(t.x - s.x) * cos(pi / 3) - (t.y - s.y) * sin(pi / 3) + s.x,
        y=(t.x - s.x) * sin(pi / 3) + (t.y - s.y) * cos(pi / 3) + s.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)


def main():
    n = int(input())
    p1 = Point(0.0, 0.0)
    p2 = Point(100.0, 0.0)
    print(p1)
    kock(n, p1, p2)
    print(p2)

main()