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



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

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

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

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

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

        return s, u, t


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


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

    s.output()

    kock(n-1, s, u)

    u.output()

    kock(n-1, u, t)

    t.output()

    kock(n-1, t, point2)




n = int(input())

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


p1.output()

kock(n, p1, p2)

p2.output()

Submission status: Accepted

Solution code:
from math import sqrt

def koch(n, c1, c2):
    if n == 0:
        return
    
    # 処理
    v = [c2[0] - c1[0], c2[1] - c1[1]]

    s = [c1[0] + v[0] / 3, c1[1] + v[1] / 3]
    t = [c1[0] + 2 * v[0] / 3, c1[1] + 2 * v[1] / 3]
    u = [c1[0] + v[0]/2 - v[1] * sqrt(3) / 6, c1[1] + v[1]/2 + v[0] * sqrt(3) / 6]

    koch(n-1, c1, s)
    print(" ".join(map(str, s)))
    koch(n-1, s, u)
    print(" ".join(map(str, u)))
    koch(n-1, u, t)
    print(" ".join(map(str, t)))
    koch(n-1, t, c2)


    

def main():
    fmt = "%.8f %.8f"
    q3 = sqrt(3)

    c1 = [0, 0]
    c2 = [100, 0]

    n = int(input())
    print(fmt % tuple(c1))
    koch(n, c1, c2)
    print(fmt % tuple(c2))

main()

Submission status: Accepted

Solution code:
def devide2points(p1,p2):
    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=((p1[0]+p2[0])/2-(p2[1]-p1[1])*(3**(1/2))/6,(p1[1]+p2[1])/2+(p2[0]-p1[0])*(3**(1/2))/6)
    return [s,u,t]

def divide(points):
    res = [points[0]]
    for i in range(len(points)-1):
        res = res + devide2points(points[i],points[i+1]) + [points[i+1]]
    return res

n = int(input())
points = [(0.0,0.0),(100.0,0.0)]
for _ in range(n):
    points = divide(points)
for i in points:
    print(i[0],i[1])

Submission status: Accepted

Solution code:
import math

n = int(input())

def foo(p1, p2):
    s_x = p1[0] + (p2[0] - p1[0]) / 3.0
    s_y = p1[1] + (p2[1] - p1[1]) / 3.0
    t_x = p1[0] + (2 * (p2[0] - p1[0])) / 3.0
    t_y = p1[1] +  (2 * (p2[1] - p1[1])) / 3.0
    u_x = math.cos(math.radians(60)) * (t_x - s_x) - math.sin(math.radians(60)) * (t_y - s_y) + s_x
    u_y = math.sin(math.radians(60)) * (t_x - s_x) + math.cos(math.radians(60)) * (t_y - s_y) + s_y

    return [[s_x, s_y], [u_x, u_y], [t_x, t_y]]

def bar(arr):
    result = []
    for i in range(len(arr) - 1):
        result.append(arr[i])
        result.extend(foo(arr[i], arr[i + 1]))
    result.append(arr[-1])
    return result

result = [[0, 0], [100.0, 0]]

for i in range(n):
    result = bar(result)

for ret in result:
    print("{} {}".format(ret[0], ret[1]))

Submission status: Accepted

Solution code:
import math

n = int(input())

dots = [[0,0],[100,0]]
for _ in range(n):
    producedDots = []
    for i in range(len(dots)-1):
        pointA = [dots[i][0] + (dots[i+1][0]-dots[i][0])/3, dots[i][1] + (dots[i+1][1]-dots[i][1])/3]
        pointB = [dots[i][0] + (dots[i+1][0]-dots[i][0])*2/3, dots[i][1] + (dots[i+1][1]-dots[i][1])*2/3]

        producedDots.append(dots[i])
        producedDots.append(pointA)

        arrow = [pointB[0]-pointA[0], pointB[1]-pointA[1]]
        cos60 = math.cos(math.radians(60))
        sin60 = math.sin(math.radians(60))
        newArrow = [arrow[0]*cos60 - arrow[1]*sin60, arrow[0]*sin60 + arrow[1]*cos60]
        pointC = [pointA[0] + newArrow[0], pointA[1] + newArrow[1]]
        producedDots.append(pointC)

        producedDots.append(pointB)
    dots = producedDots
    dots.append([100,0])

for _ in dots:
    print(" ".join(map(str,_)))

Submission status: Accepted

Solution code:
import math

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


def koch(n, a, b):
    if n == 0:
        return
    th = math.radians(60)
    s = Point((2*a.x+b.x)/3, (2*a.y+b.y)/3)
    t = Point((a.x+2*b.x)/3, (a.y+2*b.y)/3)
    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(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__':
    import sys
    input = sys.stdin.readline

    n = int(input())

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

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

Submission status: Accepted

Solution code:
def koch(p,q,n):
    if n==0:
        return [p]
    else:
        c1=[(p[0]*2+q[0])/3,(p[1]*2+q[1])/3]
        c3=[(p[0]+q[0]*2)/3,(p[1]+q[1]*2)/3]
        if p[0]<q[0]:
            if p[1]==q[1]:
                c2=[(p[0]+q[0])/2,p[1]+(q[0]-p[0])/2/3**0.5]
            elif p[1]<q[1]:
                c2=[p[0],(p[1]+q[1]*2)/3]
            else:
                c2=[q[0],(p[1]*2+q[1])/3]
        else:
            if p[1]==q[1]:
                c2=c2=[(p[0]+q[0])/2,p[1]+(q[0]-p[0])/2/3**0.5]
            elif p[1]<q[1]:
                c2=[q[0],(p[1]*2+q[1])/3]
            else:
                c2=[p[0],(p[1]+q[1]*2)/3]
        return koch(p,c1,n-1)+koch(c1,c2,n-1)+koch(c2,c3,n-1)+koch(c3,q,n-1)


n=int(input())
ans=koch([0,0],[100,0],n)+[[100,0]]
for i in ans:
    print(*i)

Submission status: Accepted

Solution code:
n = int(input())
L = [[0,0],[100,0]]
for i in range(n):
    sub = []
    for j in range(len(L)-1):
        K = []
        a = L[j][0]
        b = L[j][1]
        c = L[j+1][0]
        d = L[j+1][1]
        if a == 0:
            K.append([a,b])
        K.append([a+((c-a)/3),b+((d-b)/3)])
        K.append([(a+c)/2+(b-d)*(3**0.5)/6,(b+d)/2+(c-a)*(3**0.5)/6])
        K.append([a+((c-a)*2/3),b+((d-b)*2/3)])
        K.append([c,d])
        sub = sub+K
    L = sub
for i in range(len(L)):
    print(L[i][0],L[i][1])

Submission status: Accepted

Solution code:
from math import sqrt
from functools import reduce

N = int(input())

def koch(p1, p2, n):
	if n == 0:
		return [p1, p2]
	else:
		c1 = [(2*p1[0] + p2[0])/3, (2*p1[1] + p2[1])/3]
		c3 = [(p1[0] + 2*p2[0])/3, (p1[1] + 2*p2[1])/3]
		c2 = [(p1[0] + p2[0]) / 2 + 1/sqrt(3) * (p1[1] - p2[1])/2, (p1[1] + p2[1]) / 2 + 1/sqrt(3) * (p2[0] - p1[0])/2]
		return koch(p1, c1, n-1)[:-1] + koch(c1, c2, n-1)[:-1] + koch(c2, c3, n-1)[:-1] + koch(c3, p2, n-1)


for p in koch([0.0, 0.0], [100.0, 0.0], N):
	print('{:.6f} {:.6f}'.format(p[0], p[1]))

Submission status: Accepted

Solution code:
n = int(input())

def drawKoch(p1, p2, i):
    if i == 0:
        print(*p1)
        return 0
    else:
        s = [p2[0]/3+p1[0]*2/3, p2[1]/3+p1[1]*2/3]
        t = [p2[0]*2/3+p1[0]/3, p2[1]*2/3+p1[1]/3]
        u = [p2[0]/2+p1[0]/2-(p2[1]-p1[1])/(2*(3**0.5)), \
            p2[1]/2+p1[1]/2+(p2[0]-p1[0])/(2*(3**0.5))]
        drawKoch(p1, s, i-1)
        drawKoch(s,  u, i-1)
        drawKoch(u,  t, i-1)
        drawKoch(t, p2, i-1)

p1_start = [0.0, 0.0]
p2_start = [100.0, 0.0]
drawKoch(p1_start, p2_start, n)
print(*p2_start)

Submission status: Accepted

Solution code:
import math
SIN_T = math.sin(math.pi / 3)
COS_T = math.cos(math.pi / 3)


def koch(p0, p4):
    p1 = ((p0[0]*2 + p4[0])/3, (p0[1]*2 + p4[1])/3)
    p3 = ((p0[0] + p4[0]*2)/3, (p0[1] + p4[1]*2)/3)
    p2 = (COS_T*(p3[0]-p1[0]) + -SIN_T*(p3[1]-p1[1]) + p1[0],
          SIN_T*(p3[0]-p1[0]) + COS_T*(p3[1]-p1[1]) + p1[1])

    return [p1, p2, p3, p4]


if __name__ == "__main__":
    n = int(input())
    points = [(0, 0), (100, 0)]

    for _ in [0]*n:
        _points = [points[0]]
        for origin, dest in zip(points, points[1:]):
            _points += koch(origin, dest)

        points = _points

    for p in points:
        print(*p)

Submission status: Accepted

Solution code:
import math
n = int(input())
pi = math.pi
def distance(p1, p2):
  print(math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2))
  return math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)

def koch(p1, p2):
  p3 = [0, 0]
  p4 = [0, 0]
  p5 = [0, 0]
  p3[0] = round((p1[0]*2 + p2[0]) / 3, 8)
  p3[1] = round((p1[1]*2 + p2[1]) / 3, 8)
  p4[0] = round((p1[0] + p2[0]*2) / 3, 8)
  p4[1] = round((p1[1] + p2[1]*2) / 3, 8)
  p5[0] = round((p4[0]-p3[0])*math.cos(pi/3)-(p4[1]-p3[1])*math.sin(pi/3)+p3[0], 8)
  p5[1] = round((p4[0]-p3[0])*math.sin(pi/3)+(p4[1]-p3[1])*math.cos(pi/3)+p3[1], 8)
  return p3, p4, p5

dots = [[0,0], [100,0]]
def loop(p1, p2, i):
  if i == n:
    return 

  p3, p4, p5= koch(p1, p2)
  dots.append(p3)
  dots.append(p4)
  dots.append(p5)
  loop(p1, p3, i+1)
  print(*p3) 
  loop(p3, p5, i+1)
  print(*p5)
  loop(p5, p4, i+1)
  print(*p4)
  loop(p4, p2, i+1)
  
print(0, 0)
loop([0,0], [100, 0], 0)
print(100, 0)

Submission status: Accepted

Solution code:
import math
def kochCurve(d, p1, p2):
    if d <= 0:
        return
    s = [(2.0*p1[0]+1.0*p2[0])/3.0, (2.0*p1[1]+1.0*p2[1])/3.0]
    t = [(1.0*p1[0]+2.0*p2[0])/3.0, (1.0*p1[1]+2.0*p2[1])/3.0]
    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]]
    kochCurve(d-1, p1, s)
    print(s[0], s[1])
    kochCurve(d-1, s, u)
    print(u[0], u[1])
    kochCurve(d-1, u, t)
    print(t[0], t[1])
    kochCurve(d-1, t, p2)
n = int(input())
s = [0.00000000, 0.00000000]
e = [100.00000000, 0.00000000]
print(s[0],s[1])
if n != 0:
    kochCurve(n,s,e)
print(e[0],e[1])

Submission status: Accepted

Solution code:
import math

def koch(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
    theta = math.pi/3  #180[deg] == math.pi[rad]
    ux = math.cos(theta)*(tx-sx) - math.sin(theta)*(ty-sy)+sx
    uy = math.sin(theta)*(tx-sx) + math.cos(theta)*(ty-sy)+sy

    koch(n-1, p1x, p1y, sx, sy)
    print("{:.5f} {:.5f}".format(sx, sy))
    koch(n-1, sx, sy, ux, uy)
    print("{:.5f} {:.5f}".format(ux, uy))
    koch(n-1, ux, uy, tx, ty)
    print("{:.5f} {:.5f}".format(tx, ty))
    koch(n-1, tx, ty, p2x, p2y)

n = int(input())
p1x,p1y = 0.0,0.0
p2x,p2y = 100.0,0.0
print("{:.5f} {:.5f}".format(p1x, p1y))
koch(n, p1x, p1y, p2x, p2y)
print("{:.5f} {:.5f}".format(p2x, p2y))

Submission status: Accepted

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

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


def koch(d, p1, p2):
    if d == 0:
        return
    s = [
        (2.0*p1[0]+1.0*p2[0])/3.0,
        (2.0*p1[1]+1.0*p2[1])/3.0
    ]
    t = [
        (1.0*p1[0]+2.0*p2[0])/3.0,
        (1.0*p1[1]+2.0*p2[1])/3.0
    ]
    u = [
        (t[0]-s[0])*cos60 - (t[1]-s[1])*sin60 + s[0],
        (t[0]-s[0])*sin60 + (t[1]-s[1])*cos60 + s[1]
    ]

    koch(d-1, p1, s)
    print(f"{s[0]} {s[1]}")
    koch(d-1, s, u)
    print(f"{u[0]} {u[1]}")
    koch(d-1, u, t)
    print(f"{t[0]} {t[1]}")
    koch(d-1, t, p2)
    return


print(f"{0} {0}")
koch(n, [0, 0], [100, 0])
print(f"{100} {0}")

Submission status: Accepted

Solution code:
def koch_curve(point1, point2, N):
    if N == 0:
        print('{:8f} {:8f}'.format(point1[0], point1[1]))
        return
    pointS = ((2 * point1[0] + point2[0]) / 3,
              (2 * point1[1] + point2[1]) / 3)
    pointT = ((point2[0] - point1[0]) / 2 - (point2[1] - point1[1]) / 3.46410161514 + point1[0],
              (point2[0] - point1[0]) / 3.46410161514 + (point2[1] - point1[1]) / 2 + point1[1])
    pointU = ((point1[0] + 2 * point2[0]) / 3,
              (point1[1] + 2 * point2[1]) / 3)
    if N > 1:
        koch_curve(point1, pointS, N - 1)
        koch_curve(pointS, pointT, N - 1)
        koch_curve(pointT, pointU, N - 1)
        koch_curve(pointU, point2, N - 1)
    else:
        print('{:8f} {:8f}'.format(point1[0], point1[1]))
        print('{:8f} {:8f}'.format(pointS[0], pointS[1]))
        print('{:8f} {:8f}'.format(pointT[0], pointT[1]))
        print('{:8f} {:8f}'.format(pointU[0], pointU[1]))


N = int(input())
koch_curve((0.0, 0.0), (100.0, 0.0), N)
print('100.00000000 0.00000000')

Submission status: Accepted

Solution code:
import cmath

cmp_s = cmath.rect(1/3, 0)
cmp_u = cmath.rect(3**(-1/2), cmath.pi / 6)
cmp_t = cmath.rect(2/3, 0)


def koch_curve(p1: complex, p2: complex, n):
    if n != 0:
        cmp = p2 - p1
        s, u, t = [p1 + cmp * c for c in (cmp_s, cmp_u, cmp_t)]
        koch_curve(p1, s, n-1)
        print('{0:8f} {1:8f}'.format(s.real, s.imag))
        koch_curve(s, u, n-1)
        print('{0:8f} {1:8f}'.format(u.real, u.imag))
        koch_curve(u, t, n-1)
        print('{0:8f} {1:8f}'.format(t.real, t.imag))
        koch_curve(t, p2, n-1)


def main():
    n = int(input())
    print('{0:8f} {1:8f}'.format(.0, .0))
    koch_curve(complex(.0, .0), complex(100.0, .0), n)
    print('{0:8f} {1:8f}'.format(100.0, .0))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
def drawKoch(p1, p2, N):
    s = Point((2*p1.x+p2.x)/3,(2*p1.y+p2.y)/3)
    t = Point((p1.x+2*p2.x)/3,(p1.y+2*p2.y)/3)
    xx = t.x - s.x
    yy = t.y - s.y
    u = Point(s.x + xx/2 - yy*math.sqrt(3)/2, s.y + xx*math.sqrt(3)/2 + yy/2)
    if N > 1:
        drawKoch(p1, s, N-1)
        drawKoch(s, u, N-1)
        drawKoch(u, t, N-1)
        drawKoch(t, p2, N-1)
    else:
        printPoint(p1)
        printPoint(s)
        printPoint(u)
        printPoint(t)

def printPoint(p):
    print("{0:.8f} {1:.8f}".format(p.x, p.y))

n = int(input().rstrip())
p1 = Point(0,0)
p2 = Point(100,0)
if n == 0:
    printPoint(p1)
    printPoint(p2)
else:
    drawKoch(p1, p2, n)
    printPoint(p2)

Submission status: Accepted

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

def print_tuple(t):
    print('{} {}'.format(t[0], t[1]))

def describe(depth, p1, p2):
    if(depth == 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_x = (t[0] - s[0]) * math.cos(math.radians(60)) - (t[1] - s[1]) * math.sin(math.radians(60)) + s[0]
    u_y = (t[0] - s[0]) * math.sin(math.radians(60)) + (t[1] - s[1]) * math.cos(math.radians(60)) + s[1]
    u = (u_x, u_y)

    describe(depth - 1, p1, s)
    print_tuple(s)
    describe(depth - 1, s, u)
    print_tuple(u)
    describe(depth - 1, u, t)
    print_tuple(t)
    describe(depth - 1, t, p2)

N = int(input())
start = (0.0, 0.0)
end = (100., 0.)
print_tuple(start)
describe(N, start, end)
print_tuple(end)

Submission status: Accepted

Solution code:
from sys import stdin
from math import sin, cos, pi

def kock(n, p1, p2):
    if n != 0:
        s = ( (2.0*p1[0]+p2[0])/3.0, (2.0*p1[1]+p2[1])/3.0 )
        t = ( (p1[0]+2.0*p2[0])/3.0, (p1[1]+2.0*p2[1])/3.0 )
        u_x = (t[0]-s[0])*cos(pi/3.0) - (t[1]-s[1])*sin(pi/3.0) + s[0]
        u_y = (t[0]-s[0])*sin(pi/3.0) + (t[1]-s[1])*cos(pi/3.0) + s[1]
        u = (u_x, u_y)

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

n = int(stdin.readline().rstrip())
p1 = (0.0, 0.0)
p2 = (100.0, 0.0)
print(*p1)
kock(n, p1, p2)
print(*p2)

Submission status: Accepted

Solution code:
from math import sin, cos, radians


def c(l, p1, p2):
    l -= 1
    if l < 0:
        return
    s = ((p1[0] * 2 + p2[0]) / 3, (p1[1] * 2 + p2[1]) / 3)
    c(l, p1, s)
    print(s[0], s[1])
    t = ((p1[0] + p2[0] * 2) / 3, (p1[1] + p2[1] * 2) / 3)
    dx = t[0] - s[0]
    dy = t[1] - s[1]
    u = (dx * c60 - dy * s60 + s[0], dx * s60 + dy * c60 + s[1])
    c(l, s, u)
    print(u[0], u[1])
    c(l, u, t)
    print(t[0], t[1])
    c(l, t, p2)


r = radians(60)
s60 = sin(r)
c60 = cos(r)
print(0, 0)
c(int(input()), (0, 0), (100, 0))
print(100, 0)

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}".format(self.x, self.y)

class kochCurveController:
    def insertTriangle(self,p1, p2,d):
        if d == 0:
            return
        s = self.secret(p1,p2,1,2)
        t = self.secret(p1,p2,2,1)
        u = self.calcVertex(s,t)

        self.insertTriangle(p1,s,d-1)
        print(s)
        self.insertTriangle(s,u,d-1)
        print(u)
        self.insertTriangle(u,t,d-1)
        print(t)
        self.insertTriangle(t,p2,d-1)


    def calcVertex(self,s,t):
        x = t.x - s.x
        y = t.y - s.y
        return Point(s.x+math.cos(math.radians(60))*x -math.sin(math.radians(60))*y, s.y+math.sin(math.radians(60))*x+math.cos(math.radians(60))*y)

    def secret(self,va,vb,a,b):
        return Point((b*(va.x)+a*(vb.x))/(a+b),(b*(va.y)+a*(vb.y))/(a+b))


K = kochCurveController()
N = int(input())
print(Point(0,0))
K.insertTriangle(Point(0,0),Point(100,0),N)
print(Point(100,0))

Submission status: Accepted

Solution code:
from math import sin, cos, radians

depth = int(input())


def kock(n: int, p1x: float, p1y: float, p2x: float, p2y: float)-> None:
    if n == 0:
        return

    #  p1, p2 から s, t, u を計算
    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) * cos(radians(60)) - (ty - sy) * sin(radians(60)) + sx
    uy = (tx - sx) * sin(radians(60)) + (ty - sy) * cos(radians(60)) + sy
    kock(n - 1, p1x, p1y, sx, sy)
    print(f'%10.7f %10.7f' % (sx, sy))
    kock(n - 1, sx, sy, ux, uy)
    print(f'%10.7f %10.7f' % (ux, uy))
    kock(n - 1, ux, uy, tx, ty)
    print(f'%10.7f %10.7f' % (tx, ty))
    kock(n - 1, tx, ty, p2x, p2y)


print(f'%1.7f %1.7f' % (0.0, 0.0))
kock(depth, 0.0, 0.0, 100.0, 0.0)
print(f'%10.7f %10.7f' % (100.0, 0.0))

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


def koch(p1, p2):
    d = ((p2[0] - p1[0]) / 3, (p2[1] - p1[1]) / 3)
    s = (p1[0] + d[0], p1[1] + d[1])
    t = (p1[0] + d[0] * 2, p1[1] + d[1] * 2)
    u = (
        s[0] + (1 / 2) * d[0] - (math.sqrt(3) / 2) * d[1],
        s[1] + (math.sqrt(3) / 2) * d[0] + (1 / 2) * d[1]
    )
    return [p1, s, u, t]


ps = [(0, 0), (100, 0)]
n = int(sys.stdin.readline())
for _ in range(n):
    points = []
    for i in range(len(ps) - 1):
        points += koch(ps[i], ps[i + 1])
    points += [ps[-1]]
    ps = points

for p in ps:
    print(' '.join('{0:.8f}'.format(x) for x in p))

Submission status: Accepted

Solution code:
#  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_C&lang=jp
#  Koch Curve : python3
#  2018.12.09 yonezawa


#from collections import deque
import sys
input = sys.stdin.readline
import cProfile
from math import cos,sin,radians

t = set()
def koch(n,st,ed):
    if (n == 0 ):
        print ('{:.8f} {:.8f}'.format(*ed))
        return
    s1 = st
    s5 = ed
    (x1,y1) = st
    (x5,y5) = ed

    x2 = x1 + (x5 - x1) / 3.0
    y2 = y1 + (y5 - y1)  / 3.0
    s2 = (x2,y2)

    x4 = x1 + ((x5 -x1 ) / 3.0 ) * 2
    y4 = y1 + ((y5 - y1) / 3.0 ) * 2
    s4 = (x4,y4)

    x3 = (x4-x2) * cos(radians(60)) - (y4-y2 ) * sin(radians(60)) + x2
    y3 = (x4-x2) * sin(radians(60)) + (y4-y2 ) * cos(radians(60)) + y2
    s3 = (x3,y3)

    t.add(s1)
    t.add(s2)
    t.add(s3)
    t.add(s4)
    t.add(s5)
    #print ("n=",n,*s1)
    koch (n-1,s1,s2)
    #print ("n=",n,*s2)
    koch (n-1,s2,s3)
    #print ("n=",n,*s3)
    koch (n-1,s3,s4)
    #print ("n=",n,*s4)
    koch (n-1,s4,s5)
    #print ("n=",n,*s5)

def main():
    n = int(input())
#    if ( n == 0):
#        print ('{:.8f} {:.8f}'.format(0,0))
#        print ('{:.8f} {:.8f}'.format(100,0))
#        return
    print ('{:.8f} {:.8f}'.format(0,0))
    koch(n,(0,0),(100,0))

#    l = sorted(t)
#    for i in l:
#        print ('{:.8f} {:.8f}'.format(*i))
if __name__ == '__main__':
    main()
    #pr = cProfile.Profile()
    #pr.runcall(main)
    #pr.print_stats()

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
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 = [(2*x0+x1)/3,(2*y0+y1)/3]
        c3 = [(x0+2*x1)/3,(y0+2*y1)/3]
        c2 = [(3*(x1+x0) -(y1-y0)*math.sqrt(3))/6,((x1-x0)*math.sqrt(3)+3*(y1+y0))/6]
        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:
import math
import copy
def koch(x1,y1,x2,y2):
    x3,y3 = (x1*2+x2)/3, (y1*2+y2)/3
    x4,y4 = (x1+x2*2)/3, (y1+y2*2)/3
    x5, y5 = x3 + (x4-x3)/2-((y4-y3)*math.sqrt(3))/2, y3 + ((x4-x3)*math.sqrt(3))/2+(y4-y3)/2
    return x3, y3, x4, y4, x5, y5

n = int(input())
a = [[0,0],[100,0]]
b = copy.copy(a)
for _ in range(n):
    b = copy.copy(a)
    for i in range(len(b)-1):
        x3,y3,x4,y4,x5,y5 = koch(b[i][0],b[i][1],b[i+1][0],b[i+1][1])
        a.insert(4*i+1,[x3,y3])
        a.insert(4*i+2, [x5,y5])
        a.insert(4*i+3, [x4,y4])

for i in a:
    i = list(map(str, i))
    print(' '.join(i))

Submission status: Accepted

Solution code:
import math
n = int(input())
pi = math.acos(-1)
th = pi/3


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


def koch(n, a, b):
        if n == 0:
            return 0
        s = point((2*a.x+1*b.x)/3, (2*a.y+1*b.y)/3)
        t = point((1*a.x+2*b.x)/3, (1*a.y+2*b.y)/3)
        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(n-1, a, s)
        print("{:.8f} {:.8f}".format(s.x, s.y))
        koch(n-1, s, u)
        print("{:.8f} {:.8f}".format(u.x, u.y))
        koch(n-1, u, t)
        print("{:.8f} {:.8f}".format(t.x, t.y))
        koch(n-1, t, b)


a = point(round(0, 8), round(0, 8))
b = point(round(100, 8), round(0, 8))
print("{:.8f} {:.8f}".format(a.x, a.y))
koch(n, a, b)
print("{:.8f} {:.8f}".format(b.x, b.y))

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


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

    s = [p1[0]*2/3+p2[0]/3, p1[1]*2/3+p2[1]/3]
    u = [(p1[0]+p2[0])/2+(p1[1]-p2[1])*math.sqrt(3)/6,
         (p1[1]+p2[1])/2+(p2[0]-p1[0])*math.sqrt(3)/6]
    t = [p1[0]/3+p2[0]*2/3, p1[1]/3+p2[1]*2/3]
    if k==1:
        print('{0:.8f} {1:.8f}'.format(p1[0],p1[1]))
        print('{0:.8f} {1:.8f}'.format(s[0],s[1]))
        print('{0:.8f} {1:.8f}'.format(u[0],u[1]))
        print('{0:.8f} {1:.8f}'.format(t[0],t[1]))
    elif k>0:
        koch(k-1,p1,s)
        koch(k-1,s,u)
        koch(k-1,u,t)
        koch(k-1,t,p2)
    if k==n:
        print('{0:.8f} {1:.8f}'.format(p2[0],p2[1]))

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

Submission status: Accepted

Solution code:
# coding: utf-8
from math import pi, cos, sin
    
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __str__(self):
        return str(self.x) + " " + str(self.y)
        
    def __add__(self, p):
        return Point(self.x + p.x, self.y + p.y)
    
    def __sub__(self, p):
        return Point(self.x - p.x, self.y - p.y)
    
    def __mul__(self, scala):
        return Point(self.x * scala, self.y * scala)
        
    def __div__(self, scala):
        return Point(self.x / scala, self.y / scala)
        
    def __truediv__(self, scala):
        return self.__div__(scala)
    
    def rotate(self, theta: float, origin: "Point"):
        if origin == None:
            origin = Point(0, 0)
        _self = self - origin
        x = _self.x * cos(theta) - _self.y * sin(theta)
        y = _self.x * sin(theta) + _self.y * cos(theta)        
        return Point(x, y) + origin


def dump(points: [Point]):
    for p in points:
        print(p)
        

def koch(points: [Point], n: int) -> [Point]:
    if n <= 0: return points
    if len(points) <= 1: return points
    
    _points = __koch(points)
    return koch(_points[0:2], n - 1) + \
        koch(_points[1:3], n - 1)[1:] + \
        koch(_points[2:4], n - 1)[1:] + \
        koch(_points[3:5], n - 1)[1:]


def tertile(pair: [Point, Point]) -> [Point, Point, Point, Point]:
    t1 = pair[0] + (pair[1] - pair[0]) / 3;
    t2 = pair[0] + (pair[1] - pair[0]) * 2 / 3;
    return [pair[0], t1, t2, pair[1]];
    

def __koch(pair: [Point, Point]) -> [Point, Point, Point, Point, Point]:
    four = tertile(pair)
    mid = four[1].rotate(-pi/3, four[2])
    return four[:2] + [mid] + four[2:]
        
def main():
    points = [Point(0, 0), Point(100, 0)]
    dump(koch(points, int(input())))
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
sin60 = 3 ** 0.5 / 2
cos60 = 1 / 2

def kach(d, A, B):
    if d == n:
        print('{0:.8f} {1:.8f}'.format(*B))
        return True
    x0, y0 = A
    x1, y1 = B

    dx = (x1 - x0) / 3
    dy = (y1 - y0) / 3

    sx = x0 + dx
    sy = y0 + dy

    tx = x0 + 2 * dx
    ty = y0 + 2 * dy

    ux = sx + (dx * cos60 - dy * sin60)
    uy = sy + (dx * sin60 + dy * cos60)

    S, T, U = (sx, sy), (tx, ty), (ux, uy)
    d += 1
    kach(d, A, S), kach(d, S, U), kach(d, U, T), kach(d, T, B)
start = (0.0, 0.0)
end = (100.0, 0.0)
print('{0:.8f} {1:.8f}'.format(*start))
kach(0, start, end)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 22 14:29:49 2018

@author: maezawa
"""

n = int(input())

p0 = [0, 0]
p1 = [100, 0]

def koch(edge):
    #print(edge)
    p0 = edge[0]
    p1 = edge[1]
    s = [0,0]
    t = [0,0]
    u = [0,0]
    u1 = [0,0]
    u2 = [0,0]
    s[0] = (p1[0] - p0[0])/3 + p0[0] 
    s[1] = (p1[1] - p0[1])/3 + p0[1]
    t[0] = (p1[0] - p0[0])*2/3 +p0[0]
    t[1] = (p1[1] - p0[1])*2/3 +p0[1]
    u1[0] = (p0[0] + p1[0])/2
    u1[1] = (p0[1] + p1[1])/2
    u2[0] = p0[1]-s[1]
    u2[1] = s[0]-p0[0]
    u[0] = u1[0] + u2[0]*3**0.5/2
    u[1] = u1[1] + u2[1]*3**0.5/2
    return([p0,s,u,t,p1])

points = [p0, p1]

for i in range(n):
    nextpoints = []
    for edge in zip(points, points[1:]):
        k = koch(edge)
        kl = k.pop(-1)
        nextpoints.extend(k)
    nextpoints.append(kl)   
    points = nextpoints

for i in range(len(points)):
    print(*points[i], sep=' ')