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



Sample input:
1


Sample output:
0.00000000 0.00000000
33.33333333 0.00000000
50.00000000 28.86751346
66.66666667 0.00000000
100.00000000 0.00000000

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
# コッホ曲線
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])
# 	print('{:.8f} {:.8f}'.format(s[0], s[1]))
	koch(n - 1, s, u)
	print(u[0], u[1])
# 	print('{:.8f} {:.8f}'.format(u[0], u[1]))
	koch(n - 1, u, t)
	print(t[0], t[1])
# 	print('{:.8f} {:.8f}'.format(t[0], t[1]))
	koch(n - 1, t, b)

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

Submission status: Accepted

Solution code:
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 # faster input

    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]))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# コッホ曲線 Koch curve

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
def koch(d,p0,p1):
    #終了条件
    if d == n:
        return
    
    #内分点：s,t
    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
    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)
    # point.append(s)
    koch(d+1,s,u)
    print(*u)
    # point.append(u)
    koch(d+1,u,t)
    print(*t)
    # point.append(t)
    koch(d+1,t,p1)
    
p0=[0,0]
p1=[100,0]


n=int(input())

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys,collections
n = int(sys.stdin.readline())

def koch(p1,p2,n):
  if n == 0:
    return [p1,p2]
  ret = []
  #s = [(p2[0]-p1[0])/3.0+p1[0],]
  s = [(p2[0]+2*p1[0])/3.0,(p2[1]+2*p1[1])/3.0]
  #t = [2*(p2[0]-p1[0])/3.0+p1[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
# X-a = (1(x-a)-r3(y-b))/2
# X = (x+a+r3(b-y))/2
# X = (t[0]+s[0]+r3(s[1]-t[1]))/2
# Y-b = (r3(x-a)+(y-b))/2
# Y = (r3(x-a)+y+b)/2
# Y = (r3(t[0]-s[0])+t[1]+s[1])/2
print("\n".join([str(p1)+" "+str(p2) for p1,p2 in koch([0.0,0.0],[100.0,0.0],n)]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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):#p,qはリストでp[0]がx座標、p[1]がy座標
    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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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(s)
  # print(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)
  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")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#初期値
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}")

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Koch Curve
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])

    # 正三角形の頂点uの計算
    # (u-s)=R(1/3 pi) (t-s)が成り立つのでsを移行してuが計算できる。R()は回転行列で、加法定理から導出可能。
    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)