import sys
from math import *
input = sys.stdin.readline
class pt2:
def __init__(s, x, y):
s.x = x
s.y = y
def __add__(s,o):
return pt2(s.x+o.x,s.y+o.y)
def __sub__(s,o):
return pt2(s.x-o.x,s.y-o.y)
def __mul__(s,k):
return pt2(k*s.x,k*s.y)
def __truediv__(s,k):
return pt2(s.x/k,s.y/k)
def equals(s, o):
return s.x == o.x and s.y == o.y
def norm2(s):
return s.x**2+s.y**2
def norm(s):
return s.norm2()**.5
def ccw(s,o,a):
return (o.x-s.x)*(a.y-s.y)-(o.y-s.y)*(a.x-s.x)
def cross(s,o):
return s.x*o.y-s.y*o.x
def dot(s,o):
return s.x*o.x+s.y*o.y
def __lt__(s,o):
if s.x == o.x:
return s.y < o.y
return s.x < o.x
def __str__(s):
return f'{s.x} {s.y}'
def is_ear(polygon, i):
""" 특정한 꼭짓점이 Ear인지 확인 """
prev_idx = (i - 1) % len(polygon)
next_idx = (i + 1) % len(polygon)
p1, p2, p3 = polygon[prev_idx], polygon[i], polygon[next_idx]
# 삼각형이 볼록한지 확인 (외적 사용)
cross_product = (p2-p1).cross(p3-p1)
if cross_product <= 0:
return False # 오목한 부분은 Ear가 될 수 없음
# 다른 점이 삼각형 내부에 있는지 확인
triangle = [p1, p2, p3]
for j, point in enumerate(polygon):
if j not in [prev_idx, i, next_idx] and is_point_in_triangle(point, triangle):
return False # 다른 점이 삼각형 내부에 있으면 Ear가 아님
return True
def is_point_in_triangle(p, triangle):
""" 점이 삼각형 내부에 있는지 확인 (벡터 교차 사용) """
A, B, C = triangle
d1 = (p-B).cross(A-B)
d2 = (p-C).cross(B-C)
d3 = (p-A).cross(C-A)
has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)
return not (has_neg and has_pos) # 부호가 섞이면 외부에 있음
def ear_clipping_triangulation(polygon):
""" Ear Clipping을 사용한 다각형 삼각화 """
polygon = polygon[:]
triangles = []
while len(polygon) > 3:
for i in range(len(polygon)):
if is_ear(polygon, i):
prev_idx = (i - 1) % len(polygon)
next_idx = (i + 1) % len(polygon)
triangles.append([polygon[prev_idx], polygon[i], polygon[next_idx]])
polygon.pop(i) # Ear 제거
break # 새롭게 Ear 찾기 위해 루프 종료
triangles.append(polygon) # 마지막 남은 삼각형 추가
return triangles
def Area(A):
n = len(A)
A.append(A[0])
s = 0
for i in range(n):
s += A[i].x*A[i+1].y - A[i+1].x*A[i].y
return abs(s/2)
def tri_to_sq(tri,id):
global latest_id
longest = [0,1]
for i in range(1,3):
if (tri[i]-tri[(i+1)%3]).norm2() > (tri[longest[0]]-tri[longest[1]]).norm2():
longest = [i,(i+1)%3]
i,j = longest[0],longest[1]
print("scissors")
print(id,3)
latest_id += 3
print(4,tri[i],tri[j],(tri[j]+tri[(j+1)%3])/2,(tri[(j+2)%3]+tri[(j+1)%3])/2)
mid = (tri[(j+2)%3]+tri[(j+1)%3])/2 + ((tri[j]+tri[(j+1)%3])/2-(tri[(j+2)%3]+tri[(j+1)%3])/2)*((tri[(j+1)%3]-(tri[(j+2)%3]+tri[(j+1)%3])/2).dot((tri[j]+tri[(j+1)%3])/2-(tri[(j+2)%3]+tri[(j+1)%3])/2)/((tri[j]+tri[(j+1)%3])/2-(tri[(j+2)%3]+tri[(j+1)%3])/2).norm2())
print(3,(tri[j]+tri[(j+1)%3])/2,tri[(j+1)%3],mid)
print(3,(tri[(j+2)%3]+tri[(j+1)%3])/2,mid,tri[(j+1)%3])
print("tape")
print(3,latest_id-2,latest_id-1,latest_id)
latest_id += 1
wid = (tri[i]-tri[j]).norm()
hei = (mid-tri[(j+1)%3]).norm()
print(4,pt2(0,0),pt2(wid,0),pt2(wid-((tri[j]+tri[(j+1)%3])/2-mid).norm(),hei),pt2(((tri[i]+tri[(j+1)%3])/2-mid).norm(),hei))
print(3,pt2(wid-((tri[j]+tri[(j+1)%3])/2-mid).norm(),hei),pt2(wid,0),pt2(wid,hei))
print(3,pt2(((tri[i]+tri[(j+1)%3])/2-mid).norm(),hei),pt2(0,hei),pt2(0,0))
print(4,0,0,wid,0,wid,hei,0,hei)
return sq_to_sq([pt2(0,0),pt2(wid,0),pt2(wid,hei),pt2(0,hei)],w,latest_id)
def sq_to_sq(sq,w,id):
global latest_id
wid,hei = sq[2].x,sq[2].y
while wid > 2*w:
print("scissors")
print(id,2)
latest_id += 2
print(4,0,0,wid/2,0,wid/2,hei,0,hei)
print(4,wid/2,0,wid,0,wid,hei,wid/2,hei)
print("tape")
print(2,latest_id-1,latest_id)
latest_id += 1
print(4,0,0,wid/2,0,wid/2,hei,0,hei)
print(4,0,hei,wid/2,hei,wid/2,2*hei,0,2*hei)
print(4,0,0,wid/2,0,wid/2,2*hei,0,2*hei)
sq = [pt2(0,0),pt2(wid/2,0),pt2(wid/2,2*hei),pt2(0,2*hei)]
id = latest_id
wid /= 2
hei *= 2
while wid < w:
print("scissors")
print(id,2)
latest_id += 2
print(4,0,0,wid,0,wid,hei/2,0,hei/2)
print(4,0,hei/2,wid,hei/2,wid,hei,0,hei)
print("tape")
print(2,latest_id-1,latest_id)
latest_id += 1
print(4,0,0,wid,0,wid,hei/2,0,hei/2)
print(4,wid,0,2*wid,0,2*wid,hei/2,wid,hei/2)
print(4,0,0,2*wid,0,2*wid,hei/2,0,hei/2)
wid *= 2
hei /= 2
sq = [pt2(0,0),pt2(wid,0),pt2(wid,hei),pt2(0,hei)]
id = latest_id
print("scissors")
print(latest_id,3)
latest_id += 3
print(5,0,0,w,0,w,hei*(wid-w)/w,wid-w,hei,0,hei)
print(3,w,0,wid,0,w,hei*(wid-w)/w)
print(3,wid,0,wid,hei,wid-w,hei)
print("tape")
print(3,latest_id-2,latest_id-1,latest_id)
latest_id += 1
print(5,0,0,w,0,w,hei*(wid-w)/w,wid-w,hei,0,hei)
print(3,0,hei,wid-w,hei,0,hei+hei*(wid-w)/w)
print(3,w,hei*(wid-w)/w,w,hei+hei*(wid-w)/w,0,hei+hei*(wid-w)/w)
print(4,0,0,w,0,w,hei+hei*(wid-w)/w,0,hei+hei*(wid-w)/w)
return [pt2(0,0),pt2(w,0),pt2(w,hei+hei*(wid-w)/w),pt2(0,hei+hei*(wid-w)/w)],latest_id
def sq_to_tri(sq,sin1,cos1,sin2,cos2):
global latest_id
w,h = sq[2].x,sq[2].y
l1 = h*cos1/sin1
l2 = h*cos2/sin2
print("scissors")
print(latest_id,3)
print(3,0,0,l1,h,0,h)
print(3,w,0,w,h,w-l2,h)
print(4,0,0,w,0,w-l2,h,l1,h)
latest_id += 3
print("tape")
print(3,latest_id-2,latest_id-1,latest_id)
latest_id += 1
print(3,2*l1,2*h,l1,h,2*l1,h)
print(3,2*l1,2*h,2*l1,h,w-l2,h)
print(4,0,0,w,0,w-l2,h,l1,h)
print(3,0,0,w,0,2*l1,2*h)
w = 10000
S = []
T = []
l = [*map(int,input().split())]
for i in range(l[0]):
S.append(pt2(l[2*i+1],l[2*i+2]))
l = [*map(int,input().split())]
for i in range(l[0]):
T.append(pt2(l[2*i+1],l[2*i+2]))
result_lst = []
result_ids = []
S_triangles = ear_clipping_triangulation(S)
T_triangles = ear_clipping_triangulation(T)
print("scissors")
print(0,len(S_triangles))
latest_id = len(S_triangles)
for t in S_triangles:
print(3,*t)
for i in range(len(S_triangles)):
sq,sqid = tri_to_sq(S_triangles[i],i+1)
result_lst.append(sq)
result_ids.append(sqid)
print("tape")
print(len(result_lst),*result_ids)
prefix_height = 0
latest_id += 1
for sq in result_lst:
print(4,0,prefix_height,w,prefix_height,w,prefix_height+sq[2].y,0,prefix_height+sq[2].y)
prefix_height += sq[2].y
print(4,0,0,w,0,w,prefix_height,0,prefix_height) # 처음 도형 -> 직사각형
R = []
result_lst = []
result_ids = []
m = len(T_triangles)
print("scissors")
print(latest_id,m)
latest_id += m
prefix_height = 0
for tri in T_triangles:
h = Area(tri)/w
print(4,0,prefix_height,w,prefix_height,w,prefix_height+h,0,prefix_height+h)
R.append([pt2(0,prefix_height),pt2(w,prefix_height),pt2(w,prefix_height+h),pt2(0,prefix_height+h)])
prefix_height += h
temp = latest_id
for k in range(m):
tri = T_triangles[k]
longest = [0,1]
for i in range(1,3):
if (tri[i]-tri[(i+1)%3]).norm2() > (tri[longest[0]]-tri[longest[1]]).norm2():
longest = [i,(i+1)%3]
i,j = longest[0],longest[1]
print("tape")
print(1,temp-(m-k-1))
latest_id += 1
for ii in range(1,4):R[k][ii].y -= R[k][0].y
R[k][0].y = 0
print(4,*R[k])
print(4,*R[k])
R[k],nonono = sq_to_sq(R[k],(tri[i]-tri[j]).norm(),latest_id)
tempvec1,tempvec2 = tri[j]-tri[i],tri[(j+1)%3]-tri[i]
sin1,cos1 = tempvec1.cross(tempvec2)/(tempvec1.norm()*tempvec2.norm()),tempvec1.dot(tempvec2)/(tempvec1.norm()*tempvec2.norm())
tempvec1,tempvec2 = tri[i]-tri[j],tri[(j+1)%3]-tri[j]
sin2,cos2 = tempvec1.cross(tempvec2)/(tempvec1.norm()*tempvec2.norm()),tempvec1.dot(tempvec2)/(tempvec1.norm()*tempvec2.norm())
sq_to_tri(R[k],sin1,cos1,sin2,cos2)
result_ids.append(latest_id)
result_lst.append([tri[i],tri[j],tri[(j+1)%3]])
print("tape")
print(len(result_ids),*result_ids)
for tri in result_lst:
print(3,tri[0],tri[1],tri[2])
print(*l)
컴파일 시 표준 출력 (stdout) 메시지
Compiling 'scissors.py'...
=======
adding: __main__.pyc (deflated 59%)
=======
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |