Submission #1173212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173212		iamguest	Scissors and Tape (CEOI19_scissors)	Pypy 3	0 / 100	144 ms	51624 KiB

scissors

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)

Compilation message (stdout)

Compiling 'scissors.py'...

=======
  adding: __main__.pyc (deflated 59%)

=======

• Subtask 1: 0 / 5
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 10
• Subtask 6: 0 / 16
• Subtask 7: 0 / 11
• Subtask 8: 0 / 19