29259번 - 치노의 라떼 아트 만들기 스페셜 저지

치노의 라떼 아트 (Hard)에서 하트 모양을 찾던 코코아는 문득 이런 생각이 들었다. 다각형이면서 하트 모양인 라떼 아트를 아주 작고 정교하게 만들 수 없을까? 코코아의 궁금증을 해결해 주자.

다각형의 꼭짓점 $A$, $B$가 존재하여 다음의 조건을 모두 만족하는 다각형을 하트 모양으로 정의한다.

• $A$의 내각은 $180$도보다 작고, $B$의 내각은 $180$도보다 크다.
• 주어진 다각형이 직선 $AB$에 대해 대칭이다.
• 주어진 다각형을 선분 $AB$로 나누었을 때 만들어지는 두 부분은 모두 볼록 다각형이다.

$N$ ($N=100\, 000$)의 값이 주어진다.

라떼 아트를 나타내는 다각형의 꼭짓점들의 좌표를 임의의 점에서 시작하여 시계 방향 순서대로 출력한다. $i$번째 줄에는 $i$번째 점의 $x$좌표와 $y$좌표를 순서대로 출력한다.

이 다각형이 만족해야 하는 조건은 다음과 같다.

• 정확히 $N$ 개의 꼭짓점을 갖는 단순 다각형이어야 한다.
• 내각이 정확히 $180$도인 꼭짓점이 없어야 한다.
• 각 꼭짓점의 좌표 $(x,y)$는 모두 정수여야 하며, $-2\, 000\, 000\le x,y\le 2\, 000\, 000$를 만족하여야 한다.
• 위에서 정의한 하트 모양의 조건을 만족하여야 한다.