페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10348
인터랙티브
채점 보류

냅킨 접기 60s 1024MB

문제

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

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

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

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

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

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


입력

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 두 정수 N, K가 주어진 한 줄로 시작한다. 이는 초크의 냅킨을 정의하는 다각형의 꼭짓점 개수와, K-1개의 선분으로 이루어진 깔끔한 접기 패턴으로 냅킨을 나눌 영역의 개수(K)를 의미한다.

냅킨을 정의하는 다각형은, 다각형의 둘레를 시계 방향으로 따라가며 만나는 N개의 꼭짓점 목록으로 표현된다. 첫 꼭짓점은 임의로 선택된다. 다음 N줄이 그 목록을 나타내며, i번째 줄에는 두 정수 Xi, Yi가 주어진다. 이는 i번째 점이 2차원 평면에서 (Xi, Yi)에 있음을 뜻한다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, K개의 영역을 가지는 깔끔한 접기 패턴을 만들 수 있다면 y는 POSSIBLE, 그렇지 않다면 IMPOSSIBLE이다.

K개의 영역을 가지는 깔끔한 접기 패턴을 만들 수 있다면, K-1줄을 추가로 출력하여 그 접기 패턴의 선분들을 (어떤 순서로든) 나열하라. 각 줄은 서로 다른 선분 하나를 Ax Ay Bx By 형식으로 나타내야 한다. 여기서 (Ax, Ay)와 (Bx, By)는 선분의 두 끝점이며, 순서는 상관없다. Ax, Ay, Bx, By 각각은 N/D 꼴이어야 한다. 여기서 N과 D는 양의 정수(선행 0 없이 표기)이고, 공통 소인수가 없어야 하며, 유리수 N/D를 나타낸다. 또한 N과 / 사이, 그리고 /와 D 사이에는 공백이 없어야 한다.


예제 #1

4
4 2
1 1
1 2
2 2
2 1
3 2
1 1
1 2
2 1
8 2
1 3
3 5
5 5
4 4
7 3
5 1
4 2
3 1
8 2
1 3
3 5
4 4
5 5
7 3
5 1
4 2
3 1
Case #1: POSSIBLE
1/1 2/1 2/1 1/1
Case #2: POSSIBLE
1/1 1/1 3/2 3/2
Case #3: IMPOSSIBLE
Case #4: POSSIBLE
1/1 3/1 7/1 3/1
참고: 샘플 2는 테스트 세트 1에 유효하지 않다. 샘플 1만 테스트 세트 1을 실행하기 전에(평소 샘플과 같은 방식으로) 테스트된다. 또한 샘플 2는 테스트 세트 2를 실행하기 전에 테스트되지 않는다. 샘플 케이스 #1에서는 K=2인 깔끔한 접기 패턴을 점선 4개 중 아무 것으로나 그릴 수 있다: 샘플 케이스 #2에서는 K=2인 깔끔한 접기 패턴을 다음과 같이 그릴 수 있다: 샘플 케이스 #3에서는 깔끔한 접기 패턴이 없다: 샘플 케이스 #4에서는 K=2인 깔끔한 접기 패턴이 두 가지 있다: 테스트 세트 2의 샘플 케이스에서는 K=8인 깔끔한 접기 패턴을 다음과 같이 그릴 수 있다:

예제 #2

1
10 8
4 1
3 1
2 2
2 3
1 3
1 4
2 4
3 3
3 2
4 2
Case #1: POSSIBLE
3/1 1/1 4/1 2/1
3/1 1/1 3/1 2/1
2/1 2/1 3/1 2/1
2/1 2/1 3/1 3/1
2/1 3/1 3/1 3/1
2/1 3/1 2/1 4/1
1/1 3/1 2/1 4/1

출처

GCJ 2019r3 D

로그인해야 코드를 작성할 수 있어요.