제출 #1173212

#제출 시각아이디문제언어결과실행 시간메모리
1173212iamguestScissors and Tape (CEOI19_scissors)Pypy 3
0 / 100
144 ms51624 KiB
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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...