직교 다각형에 테두리 그리기

직교 다각형이란 모든 변이 90° 또는 270°의 내각으로만 만나고 구멍이 없는 다각형을 말한다. 어느 디자인 스튜디오는 이런 도형의 둘레에 하나 이상의 직교 테두리를 그려 장식한다. 각 테두리는 바로 이전 테두리(첫 번째 테두리라면 원래 도형)로부터 일정한 거리 $d$만큼 바깥쪽에, 같은 직각 방식으로 그린다. 즉 윤곽선의 모든 직선 구간을 바깥으로 $d$만큼 밀어내되 모서리는 직각으로 유지한다. 어떤 테두리와 그 이전 윤곽선 사이에 새로 생기는 영역은 각각 고유한 색으로 칠한다.

하나의 테두리는 하나 이상의 닫힌 직교 곡선으로 이루어진다. 도형에 좁게 들어간 오목한 부분이 있으면, 그 양쪽 벽을 따라 바깥으로 나아가던 테두리가 오목한 부분의 입구에서 서로 만나 그 입구를 막아 버릴 수 있다. 그러면 그 안쪽에 갇힌 테두리 부분은 나머지 테두리와 분리된 별개의 닫힌 곡선이 된다. 따라서 하나의 테두리가 여러 개의 서로 떨어진 닫힌 곡선으로 이루어질 수 있다. 입력으로 주어지는 도형은 어떤 테두리에서도 두 수평 구간(또는 두 수직 구간)이 한 점에서라도 맞닿는 일이 없도록 보장된다.

각 도형에 대해, 도형에 가장 가까운 테두리부터 바깥쪽 순서로 두 값을 구하라. 하나는 그 테두리의 길이로, 그 테두리를 이루는 모든 닫힌 곡선의 길이를 합한 값이다. 다른 하나는 그 테두리가 새로 더하는 넓이로, 그 테두리가 둘러싸는 넓이에서 바로 이전 테두리(첫 번째 테두리라면 원래 도형)가 둘러싸는 넓이를 뺀 값이다. 어떤 테두리가 막아 버린 주머니 모양 영역은 그 테두리가 둘러싸는 넓이에서 구멍으로 처리되어 색칠되는 영역에 포함되지 않는다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 세 양의 정수 $n$, $m$, $d$가 주어진다. $n$은 도형의 꼭짓점 개수이고($n \le 100$, 직교 다각형은 변의 개수와 꼭짓점의 개수가 같다), $m$은 그릴 테두리의 개수이며($m \le 20$), $d$는 이웃한 테두리 사이의 거리이다.

이어서 도형의 꼭짓점 $n$개가 각각 두 양의 정수 $x$, $y$ 좌표로 주어진다. 꼭짓점은 시계 방향으로 나열되며, $y$ 좌표가 가장 큰 꼭짓점(그런 꼭짓점이 여럿이면 그중 $x$ 좌표가 가장 작은 것)에서 시작한다. 좌표 쌍은 여러 줄에 나뉘어 주어질 수 있다.

각 테스트 케이스마다 세 줄을 출력한다.

1. Case k: (여기서 k는 1부터 세는 테스트 케이스 번호)
2. 공백 두 칸에 이어 Perimeters:, 그리고 $m$개의 테두리 길이
3. 공백 두 칸에 이어 Areas:, 그리고 $m$개의 추가 넓이

두 목록 모두 도형에 가장 가까운 테두리부터 바깥쪽 순서로, 값들을 공백 한 칸으로 구분하여 출력한다. 연속한 테스트 케이스 사이에는 빈 줄을 하나 출력한다(마지막 케이스 뒤에는 출력하지 않는다).