만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

손쉬운 다각형 프로그래밍

면접 대비

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

요약
홀수 개의 꼭짓점을 가진 다각형의 각 변의 중점이 주어질 때, 교대합과 순차 계산으로 원래 꼭짓점 좌표를 복원한다.
난이도

쉬움10점 중 3점

유형
수학, 기하, 구현, 배열
정답자
아직 제출이 없습니다

문제

NN개의 재외공관(Foreign Office)이 평면 위 서로 다른 점에 위치하며, 다각형의 꼭짓점을 이루도록 순서대로 F1,F2,…,FNF_1, F_2, \dots, F_N으로 놓여 있습니다. 이웃한 두 재외공관을 잇는 각 변의 중점에 회담 장소(meeting location)가 하나씩 놓입니다. 즉, i=1,2,…,N−1i = 1, 2, \dots, N-1에 대해 회담 장소 MiM_i는 FiF_i와 Fi+1F_{i+1}의 중점이고, MNM_N은 FNF_N과 F1F_1의 중점입니다.

NN개의 회담 장소 M1,M2,…,MNM_1, M_2, \dots, M_N의 좌표가 같은 순서로 주어질 때, NN개의 재외공관 F1,F2,…,FNF_1, F_2, \dots, F_N의 좌표를 구하세요. NN이 홀수이면 재외공관의 위치가 유일하게 결정됩니다.

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 파일의 끝까지 처리합니다. 각 테스트 케이스는 한 줄에 주어집니다. 먼저 홀수 정수 NN (3≤N3 \le N)이 오고, 이어서 2N2N개의 정수 x1 y1 x2 y2 … xN yNx_1\ y_1\ x_2\ y_2\ \dots\ x_N\ y_N이 옵니다. 여기서 (xi,yi)(x_i, y_i)는 ii번째 회담 장소 MiM_i의 좌표이며, 다각형을 따라가는 순서대로 주어집니다. 모든 좌표는 정수입니다.

출력

각 테스트 케이스마다 한 줄에 결과를 출력합니다. 먼저 정수 NN을 출력하고, 이어서 재외공관 F1,F2,…,FNF_1, F_2, \dots, F_N의 좌표를 회담 장소와 같은 순서로 출력합니다. 각 좌표 값은 소수점 아래 여섯 자리까지 출력하며, 모든 값은 공백 하나로 구분합니다.

힌트

ii번째 회담 장소는 ii번째와 (i+1)(i+1)번째 재외공관의 중점입니다(첨자는 순환하여 MNM_N은 FNF_N과 F1F_1의 중점). NN이 홀수이므로 재외공관의 위치는 다음과 같이 유일하게 복원됩니다. 먼저 교대 합 F1=M1−M2+M3−⋯+MNF_1 = M_1 - M_2 + M_3 - \dots + M_N으로 첫 번째 재외공관을 구하고, 이후 i=1,2,…,N−1i = 1, 2, \dots, N-1에 대해 Fi+1=2Mi−FiF_{i+1} = 2M_i - F_i로 나머지를 차례로 구합니다.

예제2

  1. 예제 1

    입력
    5 14 2 20 4 18 12 12 18 10 10
    3 -3 5 -2 5 -3 6
    3 -2 10 5 10 -1 12
    
    예상 출력
    5 10.000000 2.000000 18.000000 2.000000 22.000000 6.000000 14.000000 18.000000 10.000000 18.000000
    3 -4.000000 6.000000 -2.000000 4.000000 -2.000000 6.000000
    3 -8.000000 12.000000 4.000000 8.000000 6.000000 12.000000
    
  2. 예제 2

    입력
    3 2 1 2 3 0 2
    
    예상 출력
    3 0.000000 0.000000 4.000000 2.000000 0.000000 4.000000