넓이

혁신적인 제품으로 잘 알려진 어느 회사는 산업 스파이의 매력적인 표적이 될 만하다. 새로 지은 연구·개발 시설을 지키기 위해 이 회사는 부지를 순찰하는 최신 감시 로봇 시스템을 설치했다. 로봇들은 시설의 벽을 따라 이동하며 수상한 관찰 내용을 중앙 보안실에 보고한다. 경쟁사의 요원이 찾아낼 수 있는 이 시스템의 유일한 허점은, 로봇이 자신의 이동을 암호화하지 않은 채 무선으로 송신한다는 점이다. 더 이상은 알아낼 수 없는 요원은 이 정보를 이용해 새 시설이 차지한 부지의 정확한 넓이를 계산하려 한다. 건물의 모든 모서리가 직사각형 격자 위에 놓여 있고 벽은 오직 직선으로만 이루어져 있다는 사실은 공개되어 있다. 그림 1은 예시 부지를 도는 로봇의 경로를 보여 준다.

그림 1: 예시 부지.

로봇이 벽을 따라 이동한 기록으로부터 새 시설이 차지한 넓이를 계산하는 프로그램을 작성하라. 이 부지는 모서리가 직사각형 격자 위에 놓인 다각형이라고 가정해도 된다. 그런데 당신의 상사는 자신이 어디선가 찾아낸 공식을 반드시 쓰라고 고집한다. 그 공식은 다각형 내부에 있는 격자점의 개수 $I$, 변 위에 있는 격자점의 개수 $E$, 그리고 다각형의 전체 넓이 $A$를 서로 관계 짓는다. 안타깝게도 그 공식을 적어 둔 종이를 잃어버렸으니, 당신의 첫 번째 과제는 그 간단한 공식을 스스로 찾아내는 것이다.

첫 줄에는 시나리오의 개수가 주어진다.

각 시나리오의 첫 줄에는 로봇의 이동 횟수 $m$이 주어지며, $3 \le m < 100$이다. 이어지는 $m$개의 줄에는 정수 쌍 "dx dy"가 공백 하나로 구분되어 주어지고, $-100 \le \text{dx}, \text{dy} \le 100$이며 $(\text{dx}, \text{dy}) \ne (0, 0)$을 만족한다. 이 쌍은 로봇이 현재 위치를 기준으로 오른쪽으로 dx칸, 위쪽으로 dy칸 떨어진 격자점으로 이동함을 뜻한다.

로봇이 이동하는 곡선은 닫혀 있으며, 시작점과 끝점을 제외하고는 스스로 교차하거나 맞닿지 않는다고 가정해도 된다. 로봇은 건물 주위를 반시계 방향으로 돌기 때문에, 구하려는 넓이는 곡선의 왼쪽에 놓인다. 전체 다각형은 한 변의 길이가 100인 격자 위 정사각형 안에 들어간다는 것이 미리 알려져 있다.

각 시나리오에 대해, 먼저 "Scenario #i:" 형식의 줄을 출력한다. 여기서 $i$는 1부터 시작하는 시나리오 번호이다. 그다음 한 줄에 $I$, $E$, $A$를 출력한다. 각각 내부 격자점의 개수, 경계 격자점의 개수, 그리고 소수점 아래 한 자리로 반올림한 넓이 $A$이며, 세 값은 공백 하나로 구분한다. 연속한 두 시나리오 사이에는 빈 줄을 하나 넣는다.