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
import sys
class Point:
    def __init__(self):
        self.x = 0
        self.y = 0

def koch(n,a,b):
    th = math.pi*(60.0/180.0)
    if n == 0:
        return
    s = Point()
    t = Point()
    u = Point()
    s.x = (2.0*a.x + 1.0*b.x)/3
    s.y = (2.0*a.y + 1.0*b.y)/3
    t.x = (1.0*a.x + 2.0*b.x)/3
    t.y = (1.0*a.y + 2.0*b.y)/3
    u.x = (t.x-s.x)*math.cos(th) - (t.y - s.y)*math.sin(th) + s.x
    u.y = (t.x-s.x)*math.sin(th) + (t.y - s.y)*math.cos(th) + s.y
    koch(n-1,a,s)
    print(s.x,s.y)
    koch(n-1,s,u)
    print(u.x,u.y)
    koch(n-1,u,t)
    print(t.x,t.y)
    koch(n-1,t,b)

if __name__ == "__main__":
    n = int(input())
    a = Point()
    b = Point()
    a.x = 0
    a.y = 0
    b.x = 100
    b.y = 0

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

Submission status: Accepted

Solution code:
# coding: utf-8
# コッホ曲線
import math
import decimal


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

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

    koch(depth - 1, p1, s)
    print(' '.join(map(lambda x: '{:.8f}'.format(x), s)))
    koch(depth - 1, s, u)
    print(' '.join(map(lambda x: '{:.8f}'.format(x), u)))
    koch(depth - 1, u, t)
    print(' '.join(map(lambda x: '{:.8f}'.format(x), t)))
    koch(depth - 1, t, p2)


if __name__ == "__main__":
    depth = int(input())
    p1 = (decimal.Decimal(0), decimal.Decimal(0))
    p2 = (decimal.Decimal(100), decimal.Decimal(0))
    print(' '.join(map(lambda x: '{:.8f}'.format(x), p1)))
    koch(depth, p1, p2)
    print(' '.join(map(lambda x: '{:.8f}'.format(x), p2)))

Submission status: Accepted

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

def koch(d,p1_x,p2_x,p1_y,p2_y):
    if d==0:
        return 

    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)*cos60-(t_y-s_y)*sin60+s_x
    u_y=(t_x-s_x)*sin60+(t_y-s_y)*cos60+s_y
    
    koch(d-1,p1_x,s_x,p1_y,s_y)
    print(s_x,s_y)
    koch(d-1,s_x,u_x,s_y,u_y)
    print(u_x,u_y)
    koch(d-1,u_x,t_x,u_y,t_y)
    print(t_x,t_y)
    koch(d-1,t_x,p2_x,t_y,p2_y)
    
d=int(input())
p1_y=0
p1_x=0
p2_x=100
p2_y=0
print(float(p1_x),float(p1_y))
koch(d,p1_x,p2_x,p1_y,p2_y)
print(float(p2_x),float(p2_y))

Submission status: Accepted

Solution code:
def kochfunc(n1, x1, y1, x2, y2):   #関数作成
    if n1 > n-1:                      #breakの条件
        return 
    
    root3 = 1.732050807
    sx = (x1*2 + x2)/3 ; sy  = (y1*2 + y2)/3 
    tx = (x1 + x2*2)/3 ; ty  = (y1 + y2*2)/3
    
    vx = tx-sx; vy = ty-sy
    ux = sx + (vx - vy*root3)/2
    uy = sy + (vx*root3 + vy)/2
    
    kochfunc(n1+1, x1, y1, sx, sy)      #再帰関数
    print('{:.8f}'.format(sx), '{:.8f}'.format(sy))
    kochfunc(n1+1, sx, sy, ux, uy)
    print('{:.8f}'.format(ux), '{:.8f}'.format(uy))
    kochfunc(n1+1, ux, uy, tx, ty)
    print('{:.8f}'.format(tx), '{:.8f}'.format(ty))
    kochfunc(n1+1, tx, ty, x2, y2)
    
n = int(input())    
print('{:.8f}'.format(0), '{:.8f}'.format(0))    
kochfunc(0, 0, 0, 100, 0)
print('{:.8f}'.format(100), '{:.8f}'.format(0))

Submission status: Accepted

Solution code:
def koch(x0,y0, x1,y1, n):
    if n == 0:
        return [(x0,y0)]
    else:
        v = (y0-y1,x1-x0)
        #print(type(n))
        #print(n[0])
        m = ((x0+x1)/2,(y0+y1)/2)
        c1 = ((2*x0+x1)/3,(2*y0+y1)/3)
        #print(m[0],n[0],m[1],n[1])
        c2x = m[0]+v[0]/(2*(3**(1/2)))
        c2y = m[1]+v[1]/(2*(3**(1/2)))
        c2 = (c2x,c2y)
        c3 = ((x0+2*x1)/3,(y0+2*y1)/3)
        return koch(x0,y0, c1[0],c1[1], n-1) \
        + koch(c1[0],c1[1], c2[0],c2[1], n-1) \
        + koch(c2[0],c2[1], c3[0],c3[1], n-1) \
        + koch(c3[0],c3[1], x1,y1, n-1)
def show_vertex(x,y):
    print("%.8f %.8f" % (x,y))

N = int(input())
V = koch(0,0,100,0,N)+[[100,0]]
for x,y in V:
    show_vertex(x,y)

Submission status: Accepted

Solution code:
import math

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

def koch(x0, y0, x1, y1, n):
  if n ==0:
    show_vertex(x0, y0)
  else:
    c1 = [x0 + (x1-x0)/3, y0 + (y1-y0)/3]
    c3 = [x0 + 2*(x1-x0)/3, y0 + 2*(y1-y0)/3]
    c2 = [(x0 + x1)/2 + ((y0-y1)*math.sin(math.pi/3))/3, (y0 + y1)/2 + ((x1-x0)*math.sin(math.pi/3))/3]
    koch(x0,y0, c1[0],c1[1], n-1)
    koch(c1[0],c1[1], c2[0],c2[1], n-1)
    koch(c2[0],c2[1], c3[0],c3[1], n-1)
    koch(c3[0],c3[1], x1,y1, n-1)

N = int(input())
koch(0, 0, 100, 0, N)
show_vertex(100, 0)

Submission status: Accepted

Solution code:
n= int(input())
def koch(s,t,n):
    if n==0: #何回思考を繰り返したかを示す変数
        pass
    else:
        x= (t[0]-s[0])/3  # (x,y)は端点を結ぶ線分を三等分した時のベクトル
        y= (t[1]-s[1])/3
        ss= [ s[0]+ x, s[1]+ y ]  #ssはs,tの三等分点のうち、s寄りの点
        tt= [ t[0]- x, t[1]- y ]  #ttはs,tの三等分点のうち、t寄りの点
        st= [ ss[0]+ x/2- (3**0.5)*y/2 , ss[1]+ (3**0.5)*x/2+ y/2 ] #stは三角形の頂点の座標
        
        koch(s,ss,n-1) #1/3線分で再帰。nの値を１減らす
        print(ss[0],ss[1])  #点の座標を表示
        koch(ss,st,n-1)
        print(st[0],st[1])
        koch(st,tt,n-1)
        print(tt[0],tt[1])
        koch(tt,t,n-1)
    


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

Submission status: Accepted

Solution code:
N = int(input())

def solve(x1, y1, x2, y2, n):
    if n == 0:
        return print(x1, y1)
    else:
        solve(x1, y1, (2 * x1 + x2) / 3, (2 * y1 + y2) / 3, n - 1)
        solve((2 * x1 + x2) / 3, (2 * y1 + y2) / 3, (x1 + x2) / 2 + (y1 - y2) * (3 ** (1 / 2)) / 6, (y1 + y2) / 2 + (x2 - x1) * (3 ** (1 / 2)) / 6, n - 1)
        solve((x1 + x2) / 2 + (y1 - y2) * (3 ** (1 / 2)) / 6, (y1 + y2) / 2 + (x2 - x1) * (3 ** (1 / 2)) / 6, (x1 + 2 * x2) / 3, (y1 + 2 * y2) / 3, n - 1)
        solve((x1 + 2 * x2) / 3, (y1 + 2 * y2) / 3, x2, y2, n - 1)

solve(0, 0, 100, 0, N)
print(100, 0)

Submission status: Accepted

Solution code:
n=int(input())
p=[[0,0]]
r3=1.7320508
def unit_koch(p1,p2,d):
  if d>=n:
    return
  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]
  v_s_t=[t[0]-s[0],t[1]-s[1]]
  v_s_u=[v_s_t[0]/2-v_s_t[1]*r3/2,v_s_t[1]/2+v_s_t[0]*r3/2]
  u=[s[0]+v_s_u[0],s[1]+v_s_u[1]]
  unit_koch(p1,s,d+1)
  p.append(s)
  unit_koch(s,u,d+1)
  p.append(u)
  unit_koch(u,t,d+1)
  p.append(t)
  unit_koch(t,p2,d+1)
unit_koch([0,0],[100,0],0)
p.append([100,0])
for i in p:
  print(str(i[0])+' '+str(i[1]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

N = int(input())
ans = []
const = 2*3**0.5
def korch_curve(Lx,Ly,Rx,Ry,i):
    if i == 0:
        ans.append((Lx,Ly))
        return 
    third_y = (Ly*2 + Ry)/3
    third_x = (Lx*2 + Rx)/3
    korch_curve(Lx,Ly,third_x,third_y,i - 1)
    middle_x = (Lx + Rx)/2 - (Ry - Ly)/const
    middle_y = (Ly + Ry)/2 + (Rx - Lx)/const
    korch_curve(third_x,third_y,middle_x,middle_y,i - 1)
    third_second_x = (Lx + Rx*2)/3
    third_second_y = (Ly + Ry*2)/3
    korch_curve(middle_x,middle_y,third_second_x,third_second_y,i - 1)
    korch_curve(third_second_x,third_second_y,Rx,Ry,i - 1)
korch_curve(0,0,100,0,N)
ans.append((100,0))
for a in ans:
    print(*a)

Submission status: Accepted

Solution code:
def solve(i,x1,x2,y1,y2):
    global n
    if i == n:
        return print(x2,y2)
    X1 = (2*x1+x2)/3
    Y1 = (2*y1+y2)/3
    X3 = (x1+2*x2)/3
    Y3 = (y1+2*y2)/3
    X2 = (X3+X1)/2+3**(0.5)*(Y1-Y3)/2
    Y2 = (3**(0.5)*(X3-X1)+(Y1+Y3))/2
    solve(i+1,x1,X1,y1,Y1)
    solve(i+1,X1,X2,Y1,Y2)
    solve(i+1,X2,X3,Y2,Y3)
    solve(i+1,X3,x2,Y3,y2)

n = int(input())
print(0,0)
solve(0,0,100,0,0)

Submission status: Accepted

Solution code:
import math
n = int(input())
p1 = (0, 0)
p2 = (100, 0)

def kock(n, p1, p2):
    if n == 0:
        return
    
    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)
    
    ux = math.cos(math.radians(60)) * (tx-sx) - math.sin(math.radians(60)) * (ty-sy) + sx
    uy = math.sin(math.radians(60)) * (tx-sx) + math.cos(math.radians(60)) * (ty-sy) + sy
    u = (ux, uy)
    
    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)
    
print(*p1)
kock(n, p1, p2)
print(*p2)

Submission status: Accepted

Solution code:
from math import sqrt, sin, cos

def readinput():
    n=int(input())
    return n

def apex3(x1,y1,x2,y2):
    '''正三角形の残りの頂点(x3,y3)を求める
    
    1->2->3の順に反時計回り
    '''
    x3 = 1.0/2.0 *(x2-x1) -sqrt(3.0)/2.0 * (y2-y1) +x1
    y3 = sqrt(3.0)/2.0 * (x2-x1) + 1.0/2.0 * (y2-y1) +y1
    return x3,y3

def koch(x1,y1,x2,y2,l,lmax):
    #print('l:{}, lmax:{}'.format(l,lmax))
    if(l==lmax):
        return

    x3,y3=(x2-x1)/3 +x1, (y2-y1)/3 +y1
    x4,y4=(x2-x1)/3*2 +x1, (y2-y1)/3*2 +y1
    x5,y5 = apex3(x3,y3,x4,y4)

    koch(x1,y1,x3,y3,l+1,lmax)
    print('{:.10f} {:.10f}'.format(x3,y3))
    koch(x3,y3,x5,y5,l+1,lmax)
    print('{:.10f} {:.10f}'.format(x5,y5))
    koch(x5,y5,x4,y4,l+1,lmax)
    print('{:.10f} {:.10f}'.format(x4,y4))
    koch(x4,y4,x2,y2,l+1,lmax)

    return

def main(n):
    x0=0;y0=0
    x1=100;y1=0
    print('{:.10f} {:.10f}'.format(x0,y0))
    koch(x0,y0,x1,y1,0,n)
    print('{:.10f} {:.10f}'.format(x1,y1))


if __name__=='__main__':
    n=readinput()
    main(n)

Submission status: Accepted

Solution code:
import math

n = int(input())
a = [0, 0]
b = [100, 0]
root3 = math.sqrt(3)


def koch(a, b, n):
    if n == 1:
        s = [(a[0] * 2 + b[0]) / 3, (a[1] * 2 + b[1]) / 3]
        t = [(a[0] + b[0] * 2) / 3, (a[1] + b[1] * 2) / 3]
        u = [(s[0] + t[0] - root3 * t[1] + root3 * s[1]) / 2,
             (s[1] + t[1] + root3 * t[0] - root3 * s[0]) / 2]
        print(*s)
        print(*u)
        print(*t)
        print(*b)

    elif n > 1:
        s = [(a[0] * 2 + b[0]) / 3, (a[1] * 2 + b[1]) / 3]
        t = [(a[0] + b[0] * 2) / 3, (a[1] + b[1] * 2) / 3]
        u = [(s[0] + t[0] - root3 * t[1] + root3 * s[1]) / 2,
             (s[1] + t[1] + root3 * t[0] - root3 * s[0]) / 2]
        koch(a, s, n-1)
        koch(s, u, n-1)
        koch(u, t, n-1)
        koch(t, b, n-1)


print(*a)
koch(a, b, n)
if n == 0:
    print(*b)

Submission status: Accepted

Solution code:
import math

class KochCurve(object):
	# public変数
	x = 0.0
	y = 0.0

	# private変数
	#__xy = 0.0

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

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

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


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

	n = int(input())

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

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

Submission status: Accepted

Solution code:
import math


def calc_koch_curve(left, right, i):
    if i == n:
        return
    mid1 = (2*left[0] + right[0]) / 3, (2*left[1] + right[1]) / 3
    mid2 = (left[0] + 2*right[0]) / 3, (left[1] + 2*right[1]) / 3
    mid3_x = (
        (mid2[0] - mid1[0]) * math.cos(math.pi/3)
        - (mid2[1] - mid1[1]) * math.sin(math.pi/3) + mid1[0])
    mid3_y = (
        (mid2[0] - mid1[0]) * math.sin(math.pi/3)
        + (mid2[1] - mid1[1]) * math.cos(math.pi/3) + mid1[1])
    mid3 = (mid3_x, mid3_y)

    calc_koch_curve(left, mid1, i+1)
    print(*mid1)
    calc_koch_curve(mid1, mid3, i+1)
    print(*mid3)
    calc_koch_curve(mid3, mid2, i+1)
    print(*mid2)
    calc_koch_curve(mid2, right, i+1)


def main():
    global C
    global n
    C = [(0, 0)]
    n = int(input())
    print(0., 0.)
    calc_koch_curve((0, 0), (100, 0), 0)
    print(100., 0.)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
cos60 = math.cos(60/180*math.pi)
sin60 = math.sin(60/180*math.pi)
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(n, p1, p2):
    if(n==0):
        return
    s = Point((2* p1.x + p2.x)/3, (2* p1.y + 1*p2.y)/3)
    
    t = Point((p1.x + 2* p2.x)/3, (p1.y + 2* p2.y)/3)
    
    u = Point((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)

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

Submission status: Accepted

Solution code:
import math
n=int(input())
p1=(0,0)
p2=(100,0)

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

    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)

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

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

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

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

  th = pi * 60.0 / 180.0

  s, t, u = Point(0.0, 0.0), Point(0.0, 0.0), Point(0.0, 0.0)

  s.x = (2.0 * a.x + 1.0 * b.x) / 3.0
  s.y = (2.0 * a.y + 1.0 * b.y) / 3.0
  t.x = (1.0 * a.x + 2.0 * b.x) / 3.0
  t.y = (1.0 * a.y + 2.0 * b.y) / 3.0
  u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x
  u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y

  koch(n - 1, a, s)
  print(f'{s.x:,.8f} {s.y:,.8f}')

  koch(n - 1, s, u)
  print(f'{u.x:,.8f} {u.y:,.8f}')
  
  koch(n - 1, u, t)
  print(f'{t.x:,.8f} {t.y:,.8f}')

  koch(n - 1, t, b)
    

a = Point(0.0, 0.0)
b = Point(100.0, 0.0)
n = int(input())

print(f'{a.x:,.8f} {a.y:,.8f}')
koch(n,a,b)
print(f'{b.x:,.8f} {b.y:,.8f}')

Submission status: Accepted

Solution code:
import math

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

def koch(depth, p0, p1):

	if depth == 0:
		return

	sx = (2*p0[0] + 1*p1[0]) / 3
	sy = (2*p0[1] + 1*p1[1]) / 3
	s = (sx,sy)
	tx = (1*p0[0] + 2*p1[0]) / 3
	ty = (1*p0[1] + 2*p1[1]) / 3
	t = (tx,ty)

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

	#各辺でkoch関数を適用することにより、頂点を出力。出力したい部分に噛ませる。
	koch(depth-1,p0,s)
	print(*s)
	koch(depth-1,s,u)
	print(*u)
	koch(depth-1,u,t)
	print(*t)
	koch(depth-1,t,p1)
	

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

Submission status: Accepted

Solution code:
import math

x = 0
y = 1
p1 = (0, 0)
p2 = (100, 0)
sin60 = math.sin(math.radians(60))
cos60 = math.cos(math.radians(60))

n = int(input())

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

    # p1, p2 から s, t, u を計算
    s = (0, 0)
    t = (0, 0)
    u = (0, 0)
    s = ((2 * p1[x] + 1 * p2[x]) / 3, (2 * p1[y] + 1 * p2[y]) / 3)
    t = ((1 * p1[x] + 2 * p2[x]) / 3, (1 * p1[y] + 2 * p2[y]) / 3)
    u = ((t[x] - s[x])*cos60 - (t[y] - s[y])*sin60 + s[x], (t[x] - s[x])*sin60 + (t[y] - s[y])*cos60 + s[y])

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


print ('{:.8f} {:.8f}'.format(p1[x], p1[y]))
kock(n, p1, p2)
print ('{:.8f} {:.8f}'.format(p2[x], p2[y]))

Submission status: Accepted

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

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

    sx = (2*p1['x'] + 1*p2['x'])/3
    sy = (2*p1['y'] + 1*p2['y'])/3
    tx = (1*p1['x'] + 2*p2['x'])/3
    ty = (1*p1['y'] + 2*p2['y'])/3
    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
    
    s = {'x':sx, 'y':sy}
    t = {'x':tx, 'y':ty}
    u = {'x':ux, 'y':uy}

    koch(n-1,p1,s)
    print('{} {}'.format(s['x'],s['y']))
    koch(n-1, s, u)
    print('{} {}'.format(u['x'],u['y']))
    koch(n-1, u, t)
    print('{} {}'.format(t['x'],t['y']))
    koch(n-1,t,p2)

p1 = {'x':float(0),'y':float(0)}
p2 = {'x':float(100),'y':float(0)}
print('{} {}'.format(p1['x'],p1['y']))
koch(n, p1, p2)
print('{} {}'.format(p2['x'],p2['y']))

Submission status: Accepted

Solution code:
import sys
from sys import stdin
input = stdin.readline
import math

th = math.pi/3.000000000000000

n = int(input())

p1 = [0.0000000000000000,0.00000000000000000]
p2 = [100.0000000000000,0.00000000000000000]

def koch(n,p1,p2):
    if n == 0:
        return
    s =[0,0]
    t =[0,0]
    u =[0,0]

    s[0] = (2.0 * p1[0] +1.0 * p2[0]) / 3.0
    s[1] = (2.0 * p1[1] +1.0 * p2[1]) / 3.0
    t[0] = (1.0 * p1[0] +2.0 * p2[0]) / 3.0
    t[1] = (1.0 * p1[1] +2.0 * p2[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]
      # p1,p2からs,t,uの座標を計算
    koch(n-1, p1, s)
    print(s[0],s[1])
    koch(n-1, s, u)
    print(u[0],u[1])
    koch(n-1, u, t)
    print(t[0],t[1])
    koch(n-1, t, p2)

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

Submission status: Accepted

Solution code:
import math


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

    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)

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

    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)

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


n = int(input())
p1 = (0, 0)
p2 = (100, 0)
print(*p1)
kock(n , p1, p2)
print(*p2)

Submission status: Accepted

Solution code:
import math

def koch(d,p1x,p1y,p2x,p2y):
    if d == 0:
        return 0
    
    sin = math.sin(math.radians(60))
    cos = math.cos(math.radians(60))
    ax = (2 * p1x + 1 * p2x)/3 
    ay = (2 * p1y + 1 * p2y)/3 
    bx = (1 * p1x + 2 * p2x)/3 
    by = (1 * p1y + 2 * p2y)/3
    ux = (bx - ax)* cos - (by - ay)*sin + ax 
    uy = (bx - ax)* sin + (by - ay)*cos + ay

    koch(d-1,p1x,p1y,ax,ay)
    print(ax,ay)
    koch(d-1,ax,ay,ux,uy)
    print(ux,uy)
    koch(d-1,ux,uy,bx,by)
    print(bx,by)
    koch(d-1,bx,by,p2x,p2y)

d = int(input())
print(0,0)
koch(d,0,0,100,0)
print(100,0)

Submission status: Accepted

Solution code:
import math
def koch(n, p1, p2):
    if n == 0:
        return None
    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]) * 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]
    ]

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

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

Submission status: Accepted

Solution code:
import math

class Pos:
  def init(x, y):
    self.x = x
    self.y = y

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

  s, t = Pos(), Pos()
  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

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

  u = Pos()
  u.x = (t.x - s.x) * cos60 - (t.y - s.y) * sin60 + s.x
  u.y = (t.x - s.x) * sin60 + (t.y - s.y) * cos60 + s.y

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

n = int(input())

p1, p2 = Pos(), Pos()
p1.x, p1.y = 0.0, 0.0
p2.x, p2.y = 100.0, 0.0

print("{:.5f} {:.5f}".format(p1.x, p1.y))
kock(n, p1, p2)
print("{:.5f} {:.5f}".format(p2.x, p2.y))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def Koch(Px, Py, Qx, Qy, n) :
    if n == 0 :
        return
    else :
        Ax = (2 * Px + Qx) / 3
        Ay = (2 * Py + Qy) / 3
        Bx = (Px + 2 * Qx) / 3
        By = (Py + 2 * Qy) / 3
        Cx = Ax + (Bx - Ax) * math.cos(math.pi/3) - (By - Ay) * math.sin(math.pi/3) 
        Cy = Ay + (Bx - Ax) * math.sin(math.pi/3) + (By - Ay) * math.cos(math.pi/3)
        
        Koch(Px, Py, Ax, Ay, n-1)
        print(Ax, Ay)
        Koch(Ax, Ay, Cx, Cy, n-1)
        print(Cx, Cy)
        Koch(Cx, Cy, Bx, By, n-1)
        print(Bx, By)
        Koch(Bx, By, Qx, Qy, n-1)

n = int(input())
print(0, 0.00000000)
Koch(0.00000000, 0.00000000, 100.00000000, 0.00000000, n)
print(100.00000000, 0.00000000)

Submission status: Accepted

Solution code:
import math
def Koch(tops):
    n = len(tops)
    new_tops = [tops[0]]
    for i in range(n-1):
        b = [0,0]
        a = [2*tops[i][0]/3 + tops[i+1][0]/3, 2*tops[i][1]/3 + tops[i+1][1]/3]
        c = [tops[i][0]/3 + 2*tops[i+1][0]/3, tops[i][1]/3 + 2*tops[i+1][1]/3]
        b[0] = (c[0]-a[0])*math.cos(math.radians(60)) - (c[1]-a[1])*math.sin(math.radians(60)) + a[0]
        b[1] = (c[0]-a[0])*math.sin(math.radians(60)) + (c[1]-a[1])*math.cos(math.radians(60)) + a[1]
        new_tops.append(a)
        new_tops.append(b)
        new_tops.append(c)
        new_tops.append(tops[i+1])
    return new_tops

n = int(input())
tops = [[0.,0.],[100.,0.]]
for i in range(n):
    tops = Koch(tops)

for j in range(len(tops)):
    print(*tops[j], sep=' ')

Submission status: Accepted

Solution code:
import math

n = int(input())

point = [(0, 0), (100, 0)]

for i in range(n):
    len_point = len(point)
    tmp = []
    for j in range(len_point - 1):
        x1, y1 = point[j]
        x2, y2 = point[j+1]
        sx, sy = (2 * x1 + x2) / 3, (2 * y1 + y2) / 3
        tx, ty = (x1 + 2 * x2) / 3, (y1 + 2 * y2) / 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
        tmp.append((x1, y1))
        tmp.append((sx, sy))
        tmp.append((ux, uy))
        tmp.append((tx, ty)) 
    tmp.append((100, 0))
    point = tmp

for x, y in point:
    print(f"{x:.8f} {y:.8f}")

Submission status: Accepted

Solution code:
def next_math(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
math = [p1, p2]

n = int(input())
for i in range(n):
    math = next_math(math)

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

Submission status: Accepted

Solution code:
n=int(input())
p1=[float(0),float(0)]
p2=[float(100),float(0)]
cos=0.5
sin=0.866025404
def koh(d,p1,p2):
    if d==0:return True
    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-(ty-sy)*sin+sx
    uy=(tx-sx)*sin+(ty-sy)*cos+sy

    koh(d-1,p1,[sx,sy])
    print(sx, sy)
    koh(d-1,[sx,sy],[ux,uy])
    print(ux, uy)
    koh(d-1,[ux,uy],[tx,ty])
    print(tx,ty)
    koh(d-1,[tx,ty],p2)
print(p1[0],p1[1])
koh(n,p1,p2)
print(p2[0],p2[1])

Submission status: Accepted

Solution code:
import math

n = int(input())

p1 = [0.0, 0.0]
p2 = [100.0, 0.0]

def rad(r) :
    return math.radians(r)

def sin(s) :
    return math.sin(s)
    
def cos(s) :
    return math.cos(s)

def Koch(n, p1, p2) :
    if n == 0 :
        return 0
    else :
        s = [0, 0]
        t = [0, 0]
        u = [0, 0]
        
        s[0] = (p2[0] - p1[0]) / 3 + p1[0]
        s[1] = (p2[1] - p1[1]) / 3 + p1[1]
        t[0] = (p2[0] - p1[0]) / 3 * 2 + p1[0]
        t[1] = (p2[1] - p1[1]) / 3 * 2 + p1[1]
        
        u[0] = (t[0] - s[0]) * cos(rad(60)) - (t[1] - s[1]) * sin(rad(60)) + s[0]
        u[1] = (t[0] - s[0]) * sin(rad(60)) + (t[1] - s[1]) * cos(rad(60)) + s[1]
        
        Koch(n - 1, p1, s)
        pri(s[0], s[1])
        
        Koch(n - 1, s, u)
        pri(u[0], u[1])
        
        Koch(n - 1, u, t)
        pri(t[0], t[1])
        
        Koch(n - 1, t, p2)
        
def pri(x, y) :
    print(f"{x:.8f} {y:.8f}")
    
print(p1[0], p1[1])
Koch(n, p1, p2)
print(p2[0], p2[1])

Submission status: Accepted

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

def add_v(l1,l2):
    n=len(l1)
    l=[0]*n
    for i in range(n):
        l[i]=l1[i]+l2[i]
    return l

def scar_multiple_v(scalar,l):
    n=len(l)
    ans=[0]*n
    for i in range(n):
        ans[i]=l[i]*scalar
    return ans

def mat_multi_v(mat,l):
    n=len(l)
    ans=[0]*n
    for i in range(n):
        for j in range(n):
            ans[i]+=mat[i][j]*l[j]
    return ans

def make_points(tail,head):
    ans=[[0]*2 for _ in range(5)]
    ans[0]=tuple(tail)
    ans[1]=tuple(add_v(tail,scar_multiple_v(1/3,add_v(head,scar_multiple_v(-1,tail)))))

    v=scar_multiple_v(1/3,add_v(head,scar_multiple_v(-1,tail)))
    mat=[[1+math.cos(math.radians(60)),-math.sin(math.radians(60))],\
         [math.sin(math.radians(60))  ,1+math.cos(math.radians(60))]]
    ans[2]=tuple(add_v(tail,mat_multi_v(mat,v)))
    ans[3]=tuple(add_v(tail,scar_multiple_v(2/3,add_v(head,scar_multiple_v(-1,tail)))))
    ans[4]=tuple(head)
    return tuple(ans)

def make_1_coch_curve(iter,tail,head):
    points=make_points(tail,head)
    if iter == n-1:
        for i in range(len(points)-1):
            print("{} {}".format(points[i][0],points[i][1]))
            
    else:
        for i in range(4):
            make_1_coch_curve(iter+1,points[i],points[i+1])
            
if n == 0:
    print("{} {}\n{} {}".format(0,0,100,0))
else:
    make_1_coch_curve(0,[0,0],[100,0])
    print("{} {}".format(100,0))

Submission status: Accepted

Solution code:
from math import cos, sin, pi

def show(p):
    print(f'{p.real:.08} {p.imag:.08}')

def rotate(p, theta):
    return p*complex(cos(theta), sin(theta))

def go(n, p1, p2):
    if n == 0:
        return
    s = (p2 - p1)/3 + p1
    t = 2*s - p1
    u = rotate(t - s, pi/3) + s
    go(n - 1, p1, s)
    show(s)
    go(n - 1, s, u)
    show(u)
    go(n - 1, u, t)
    show(t)
    go(n - 1, t, p2)


p1 = complex(0, 0)
p2 = complex(100, 0)
show(p1)
go(int(input()), p1, p2)
show(p2)

Submission status: Accepted

Solution code:
import math
def koch(d, p1, p2):
    if d == 0:
        return

    sx = (2*p1[0]+1*p2[0])/3
    sy = (2*p1[1]+1*p2[1])/3
    s = (sx, sy)
    tx = (1*p1[0]+2*p2[0])/3
    ty = (1*p1[1]+2*p2[1])/3
    t = (tx, ty)
    rad = math.radians(60)
    ux = (t[0]-s[0])*math.cos(rad)-(t[1]-s[1])*math.sin(rad)+s[0]
    uy = (t[0]-s[0])*math.sin(rad)+(t[1]-s[1])*math.cos(rad)+s[1]
    u = (ux, uy)

    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)

d = int(input())
p1 = (0, 0)
p2 = (100, 0)
print(p1[0], p1[1])
koch(d, p1, p2)
print(p2[0], p2[1])

Submission status: Accepted

Solution code:
from math import sin, cos, radians

N = int(input())

p1 = (0, 0)
p2 = (100, 0)
th = radians(60)

def koch(n, a, b):
    global th

    if n == 0:
        return
    
    s = ((2 * a[0] + 1 * b[0]) / 3, (2 * a[1] + 1 * b[1]) / 3)
    t = ((1 * a[0] + 2 * b[0]) / 3, (1 * a[1] + 2 * b[1]) / 3)
    u = ((t[0] - s[0]) * cos(th) - (t[1] - s[1]) * sin(th) + s[0],
         (t[0] - s[0]) * sin(th) + (t[1] - s[1]) * cos(th) + s[1])

    koch(n - 1, a, s)
    print(*s)
    koch(n - 1, s, u)
    print(*u)
    koch(n - 1, u, t)
    print(*t)
    koch(n - 1, t, b)

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