초크(Chalk)는 친구들과 함께 세상의 멋진 장소를 돌아다니며 사진을 찍는 여행을 활발히 해 왔다. 가장 최근에는 유럽으로 건너가 냅킨 접기의 역사를 공부했다. 그 이후로 초크는 냅킨 접기 예술을 연습하기 위해 다양한 종류의 냅킨을 모으고 있다.

초크의 냅킨은 단순 다각형(simple polygon)으로 정의할 수 있다. 단순 다각형이란, 서로 인접한 변이 공통 꼭짓점에서 만나는 경우를 제외하고는 어떤 변도 서로 교차하지 않는 다각형을 말한다. 또한 다각형의 각 꼭짓점은 정확히 두 변 위에 있다.

초크는 냅킨을 접기 위해 먼저 그 위에 접기 패턴(folding pattern)을 그린다. 접기 패턴은 냅킨 위에 그려진 K-1개의 선분들의 집합이다. 각 선분은 냅킨을 정의하는 다각형의 경계 위에 있는 두 유리수 좌표 점을 연결하며, 다각형 내부에 완전히 포함된다. 접기 패턴의 어떤 두 선분도 (공통 끝점일 가능성을 제외하고는) 서로 닿거나 겹칠 수 없다. K-1개의 선분으로 이루어진 접기 패턴은 냅킨을 K개의 다각형 영역으로 나눈다. 두 점이 같은 영역에 속한다는 것은, 다각형의 변이나 접기 패턴의 선분과 (끝점에서조차) 교차하지 않는 어떤 연속 곡선(직선일 필요 없음)으로 두 점을 이을 수 있음을 뜻한다.

초크는 깔끔한 접기 패턴(neat folding pattern)에만 관심이 있다. 접기 패턴이 깔끔하다는 것은, 어떤 접기 선분 F와 인접한 두 영역이 F에 대해 대칭(symmetric)이라는 뜻이다. 즉, 그 선분을 따라 냅킨을 접으면 두 영역이 완벽하게 겹쳐져 정렬된다는 의미다.

아래 그림은 K=8개의 영역을 갖는 깔끔한 접기 패턴의 예를 보여 준다.

초크는 깔끔한 접기 패턴을 사용해 자신의 냅킨 컬렉션을 성공적으로 접어 왔다. 하지만 컬렉션에는 아직 깔끔한 접기 패턴을 찾지 못한 냅킨들도 있다. 그런 냅킨들 각각에 대해, K개의 영역을 가지는 깔끔한 접기 패턴을 찾아 주거나, 그런 패턴이 존재하지 않음을 판별해 주어야 한다.

#10348 upload - done - how_to_reg - component_exchange Interactive stop_circle Grading on hold

Napkin Folding timer 60s memory 1024MB

#10348
Interactive

Grading on hold

Napkin Folding 60s 1024MB