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

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

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

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

    # def __rsub__(self, other):
    #     if isinstance(other, ModInt):
    #         return ModInt(other.x - self.x)
    #     else:
    #         return ModInt(other - self.x)


def koch(n,left,right):
    if n==0:
        return 
    w = ((right-left)/3)
    s = left + w
    t = left + w*2
    center = (s+t)/2 #sとtの中点
    vec1 = (t-s)*sqrt(3)/2 #sからtへのベクトルの√3/2倍
    vec2 = P(-vec1.y, vec1.x) 
    u = center + vec2

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


    # print(*left)
    # koch(n-1,left,s)
    # print(*s)
def main():
    n = int(input())
    left = P(0,0)
    right = P(100,0)
    print(left)
    koch(n,P(0,0),P(100,0))
    print(right)
    #print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def KochCurve(p1,p2,n):
    if n==0:
        return
    s = [(2*p1[0]+p2[0])/3,(2*p1[1]+p2[1])/3]
    t = [(p1[0]+2*p2[0])/3,(p1[1]+2*p2[1])/3]
    u = [(p1[0]+p2[0])/2+((-1)*math.sqrt(3))*(p2[1]-p1[1])/6,(p1[1]+p2[1])/2+(math.sqrt(3))*(p2[0]-p1[0])/6]
    KochCurve(p1,s,n-1)
    print(f"{'{:.9f}'.format(s[0])} {'{:.9f}'.format(s[1])}")
    KochCurve(s,u,n-1)
    print(f"{'{:.9f}'.format(u[0])} {'{:.9f}'.format(u[1])}")
    KochCurve(u,t,n-1)
    print(f"{'{:.9f}'.format(t[0])} {'{:.9f}'.format(t[1])}")
    KochCurve(t,p2,n-1)

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

Submission status: Accepted

Solution code:
import math

d = int(input())

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
# AOJでnumpyが使えないから自力で内積を求める
import sys
# import numpy as np
import math

input = sys.stdin.readline
n = int(input())
# ベクトルの60度回転で使う
cos60 = math.cos(math.radians(60))
sin60 = math.sin(math.radians(60))
# k = np.array([[cos60, -(sin60)], [sin60, cos60]])
k = ([[cos60, -(sin60)], [sin60, cos60]])


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


def Koch(start, end, layer):
    layer += 1
    if layer > n:
        return
    point1 = [((end[0] - start[0]) / 3) + start[0], ((end[1] - start[1]) / 3) + start[1]]
    Koch(start, point1, layer)
    print(' '.join(map(str, point1)))
    point3 = [((end[0] - start[0]) / 3 * 2) + start[0], ((end[1] - start[1]) / 3 * 2) + start[1]]
    # vec = np.array([[point3[0] - point1[0]], [point3[1] - point1[1]]])  # vecは一旦原点に戻す
    vec = ([[point3[0] - point1[0]], [point3[1] - point1[1]]])  # vecは一旦原点に戻す
    point2 = [[k[0][0] * vec[0][0] + k[0][1] * vec[1][0]], [k[1][0] * vec[0][0] + k[1][1] * vec[1][0]]]  # 内積をとって60度左回転する
    point2 = [point2[0][0] + point1[0], point2[1][0] + point1[1]]  # 元あった点に戻す
    Koch(point1, point2, layer)
    print(' '.join(map(str, point2)))
    Koch(point2, point3, layer)
    print(' '.join(map(str, point3)))
    Koch(point3, end, layer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import math
n = int(input())
a = [0] * 2
b = [0] * 2
a[0] = 0
b[0] = 100

def koch(n, a, b):
    if n == 0:
        return
    
    s = [0] * 2
    t = [0] * 2
    u =[0] * 2
    
    s[0] = (2.0 * a[0] + 1.0 * b[0]) / 3.0
    s[1] = (2.0 * a[1] + 1.0 * b[1]) / 3.0
    t[0] = (1.0 * a[0] + 2.0 * b[0]) / 3.0
    t[1] = (1.0 * a[1] + 2.0 * b[1]) / 3.0
    u[0] = (t[0] - s[0]) * math.cos(math.pi/3) - (t[1] - s[1]) * math.sin(math.pi/3) + s[0]
    u[1] = (t[0] - s[0]) * math.sin(math.pi/3) + (t[1] - s[1]) * math.cos(math.pi/3) + s[1]
    
    koch(n - 1, a, s)
    print(s[0], s[1])
    koch(n - 1, s, u)
    print(u[0], u[1])
    koch(n - 1, u, t)
    print(t[0], t[1])
    koch(n - 1, t, b)

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

Submission status: Accepted

Solution code:
import math

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

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


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


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

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

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

Submission status: Accepted

Solution code:
# ALDS1_5_C Koch Curve
import math

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

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

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

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


n = int(input())

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

Submission status: Accepted

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

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


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


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

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math
a = math.sqrt(3) * 0.5
def koch(d, p1, p2):
    if d == 0:
        return
    else:
        s = [(2*p1[0]+p2[0])/3, (2*p1[1]+p2[1])/3]
        t = [(p1[0]+2*p2[0])/3, (p1[1]+2*p2[1])/3]
        u = [(t[0]-s[0])*0.5-(t[1]-s[1])*a+s[0], (t[0]-s[0])*a+(t[1]-s[1])*0.5+s[1]]
        koch(d-1, p1, s)
        print(s[0], s[1])
        koch(d-1, s, u)
        print(u[0], u[1])
        koch(d-1, u, t)
        print(t[0], t[1])
        koch(d-1, t, p2)

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


if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
import math

class Point:

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

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

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

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


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

Submission status: Accepted

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

def koch(n,a,b):
    if n==0:
        return
    th=math.pi*60.0/180.0
    s,t,u=[0,0],[0,0],[0,0]
    s[0]=(2.0*a[0]+1.0*b[0])/3.0
    s[1]=(2.0*a[1]+1.0*b[1])/3.0
    t[0]=(1.0*a[0]+2.0*b[0])/3.0
    t[1]=(1.0*a[1]+2.0*b[1])/3.0
    u[0]=(t[0]-s[0])*math.cos(th)-(t[1]-s[1])*math.sin(th)+s[0]
    u[1]=(t[0]-s[0])*math.sin(th)+(t[1]-s[1])*math.cos(th)+s[1]

    koch(n-1,a,s)
    print(s[0],s[1])
    koch(n-1,s,u)
    print(u[0],u[1])
    koch(n-1,u,t)
    print(t[0],t[1])
    koch(n-1,t,b)


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

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

Submission status: Accepted

Solution code:
import sys
import math

def print_point(point):

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

def koch(n,p1,p2):

	if n == 0:
		return 0

	# Calculate s,t,u from p1,p2
	s = [0,0]
	t = [0,0]
	u = [0,0]
	s[0] = (2 * p1[0] + 1 * p2[0]) / 3
	s[1] = (2 * p1[1] + 1 * p2[1]) / 3
	t[0] = (1 * p1[0] + 2 * p2[0]) / 3
	t[1] = (1 * p1[1] + 2 * p2[1]) / 3
	u[0] = (t[0] - s[0]) * math.cos(math.radians(60)) - (t[1] - s[1]) * math.sin(math.radians(60)) + s[0]
	u[1] = (t[0] - s[0]) * math.sin(math.radians(60)) + (t[1] - s[1]) * math.cos(math.radians(60)) + s[1]
	
	koch(n-1,p1,s)
	print_point(s)
	
	koch(n-1,s,u)
	print_point(u)

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

	koch(n-1,t,p2)

def test():

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

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

if __name__ == "__main__":
	test()

Submission status: Accepted

Solution code:
import math

n = int(input())

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

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

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

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

Submission status: Accepted

Solution code:
import math

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

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


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

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

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

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

Submission status: Accepted

Solution code:
import math

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import math

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


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

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

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

    return ([point3, point4, point5])



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

    rec_koch_curve(pl, depth+1, target)

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import math


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


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

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


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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import math

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

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

n = int(input())

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

Submission status: Accepted

Solution code:
import math

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

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

Submission status: Accepted

Solution code:
from functools import reduce
import math

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


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


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

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

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

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

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

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

for p in ps:
    print(*p)

Submission status: Accepted

Solution code:
import math


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


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


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

    # Get s, t, u coordinates on the complex plane.
    s = (p2 - p1) * (1 / 3) + p1
    t = (p2 - p1) * (2 / 3) + p1
    u = rot60_on_complex_plane(s, t)

    # Call the function recursively by the case of n == 0.
    create_koch_points(p1, s, n - 1)
    print_real_coordinate(s)
    create_koch_points(s, u, n - 1)
    print_real_coordinate(u)
    create_koch_points(u, t, n - 1)
    print_real_coordinate(t)
    create_koch_points(t, p2, n - 1)


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

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

Submission status: Accepted

Solution code:
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

def kock(n,p1x,p1y,p2x,p2y):
    if n == 0:
        return

    sx = (2 * p1x + 1 * p2x) / 3
    sy = (2 * p1y + 1 * p2y) / 3
    tx = (1 * p1x + 2 * p2x) / 3
    ty = (1 * p1y + 2 * p2y) / 3
    ux = (tx - sx)*math.cos(math.pi/3) - (ty - sy)*math.sin(math.pi/3) + sx
    uy = (tx - sx)*math.sin(math.pi/3) + (ty - sy)*math.cos(math.pi/3) + sy

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

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

Submission status: Accepted

Solution code:
from math import sqrt
q3 = sqrt(3)
fmt = "%.8f %.8f"
def koch(x0, y0, x1, y1, c):
    if c == n:
        return (fmt % (x0, y0),)
    xp = (x0*2 + x1) / 3
    yp = (y0*2 + y1) / 3
 
    xq = (x0 + x1*2) / 3
    yq = (y0 + y1*2) / 3
 
    dx = (x1 - x0) / 6
    dy = (y1 - y0) / 6
 
    xr = xp + (dx - dy * q3)
    yr = yp + (dx * q3 + dy)
 
    return koch(x0, y0, xp, yp, c+1) + koch(xp, yp, xr, yr, c+1) + koch(xr, yr, xq, yq, c+1) + koch(xq, yq, x1, y1, c+1)
n = int(input())
print(*koch(0, 0, 100, 0, 0)+(fmt % (100, 0),), sep='\n')

Submission status: Accepted

Solution code:
def Rot(vec):
    new=[]
    new+=[vec[0]/2-vec[1]*3**(1/2)/2]
    new+=[vec[0]*3**(1/2)/2+vec[1]/2]
    return(new)

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

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

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

    return(Out)

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

Submission status: Accepted

Solution code:
import math


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


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


if __name__ == '__main__':
    main()