적의 약점을 쏴라!

시간 제한1초메모리 제한128 MB

요약
주어진 단순 다각형마다 무게중심 좌표를 구해 소수점 여섯째 자리까지 출력합니다.
난이도

보통10점 중 4점

유형
기하
정답자
아직 제출이 없습니다

문제

새로 나온 컴퓨터 게임을 다음 학기가 시작하기 전에 끝내야 한다. 단계마다 적 로봇의 약점을 쏘아 맞혀야 하는데, 약점은 화면에 보이는 로봇 2차원 도형의 무게중심이다. 모든 로봇 도형은 밀도가 일정한 단순 다각형이라서, 프로그램으로 무게중심을 정확히 계산할 수 있다.

무게중심(COM)을 좀 더 엄밀하게 정의하자. 정사각형이나 원처럼 대칭인 도형의 무게중심은 그 중심점이다. 단순 도형 CC를 넓이가 각각 SAS_A, SBS_B인 단순 도형 AA와 BB로 나누면, CC의 무게중심은 벡터로서 다음과 같다.

COM(C)=SA×COM(A)+SB×COM(B)SA+SB\mathrm{COM}(C) = \frac{S_A \times \mathrm{COM}(A) + S_B \times \mathrm{COM}(B)}{S_A + S_B}

더 일반적으로, 넓이가 SAS_A인 단순 도형 AA의 무게중심은 다음과 같다.

COM(A)=∬Aa⃗ dsSA\mathrm{COM}(A) = \frac{\iint_A \vec{a} \, ds}{S_A}

입력

입력은 로봇 정의 여러 개로 이루어진다. 각 로봇 정의는 다각형의 꼭짓점 개수 nn이 적힌 줄로 시작한다. 로봇은 단순 다각형이므로 3≤n≤1003 \le n \le 100이다. 이어지는 nn개 줄에 꼭짓점 좌표가 시계 방향이나 반시계 방향 중 한 순서로 주어진다. 각 줄에는 공백으로 구분한 정수 두 개가 있고, 좌표의 절댓값은 100을 넘지 않는다. nn이 0인 줄은 입력의 끝을 뜻하며, 이 줄은 처리하지 않는다.

출력

입력의 ii번째 로봇마다 한 줄씩, Stage #i: x y 형식으로 무게중심 (x,y)(x, y)를 출력한다. ii는 1부터 센다. 두 좌표 모두 소수점 아래 여섯째 자리까지 반올림한다. 반올림 경계에 정확히 놓이는 좌표는 입력에 나오지 않으므로 답은 하나로 정해진다.

예제1

  1. 예제 1

    입력
    4
    0 0
    0 1
    1 1
    1 0
    3
    0 1
    1 0
    2 2
    8
    1 1
    2 1
    2 7
    3 7
    3 0
    0 0
    0 7
    1 7
    0
    
    예상 출력
    Stage #1: 0.500000 0.500000
    Stage #2: 1.000000 1.000000
    Stage #3: 1.500000 3.300000