LaLa와 마법진 (LaLa 버전)

$\color{blue}{\text{LaLa}}$의 실험실에는 마법진이 여러 개 쌓여 있다.

마법진은 특수한 잉크로 그린 단순 다각형으로 나타낼 수 있다. 볼록할 때에만 사용 가능하며, 이는 모든 내각이 $\pi$ 이하라는 뜻이다.

$\color{blue}{\text{LaLa}}$는 모든 마법진을 사용 가능한 마법진으로 바꾸려 한다. 그러나 잘못 바꾸면 마력을 모두 잃을 수 있다. 다행히 $\color{blue}{\text{LaLa}}$에게는 이 일에 딱 맞는 마법 도구가 있다.

도구는 다음과 같이 작동한다. 마법진을 넣었을 때 사용 가능하면 도구는 그렇다고 알려 준다. 사용 가능하지 않으면, 다음 두 조건을 만족하는 서로 다른 두 점 $u$, $v$를 고른다.

• $u$와 $v$는 마법진의 볼록 껍질 경계 위에 있다.
• 마법진 경계를 반시계 방향으로 따라 $u$에서 $v$까지 가는 경로 위의 점 중, $u$와 $v$를 제외하고는 볼록 껍질 경계 위에 있는 점이 없다.

그다음 도구는 $u$에서 $v$까지의 경로를 $u$와 $v$의 중점을 중심으로 $\pi$만큼 회전시킨다. 즉, 그 경로 위의 각 점 $w$는 $u+v-w$가 된다. 여기서 덧셈은 마법진이 그려진 종이의 2차원 좌표계에서 좌표별로 계산한다. 이 수정 결과도 단순 다각형이 됨에 유의하라.

$\color{blue}{\text{LaLa}}$는 변환에 시간이 얼마나 걸리는지 짜증이 났다. 빨리 마치고 낮잠을 자려고, $\color{blue}{\text{LaLa}}$는 다음을 알아냈다.

1. 마법진은 도구를 유한 번 적용하면 항상 사용 가능한 마법진이 된다.
2. 최종 마법진 위의 점 집합은 중간 수정 과정과 무관하다. 즉, 최종 마법진의 모양과 위치는 처음 마법진에 따라 정해진다.

따라서 $\color{blue}{\text{LaLa}}$는 도구로 마법진을 하나씩 손볼 필요가 없다. 대신 처음 마법진에서 도구를 적용하는 순서로 만들 수 있는 사용 가능한 마법진을 계산하고, 한 번에 바꾼다.

$\color{blue}{\text{LaLa}}$가 낮잠을 자러 갈 수 있도록 최종 마법진을 계산하는 프로그램을 작성하라.

입력은 다음 형식으로 주어진다.

$N$

$x\_0$ $y\_0$

$x\_1$ $y\_1$

$\vdots$

$x\_{N-1}$ $y\_{N-1}$

처음 마법진은 각 $0 \le i < N$에 대해 점 $(x\_i, y\_i)$와 $(x\_{(i+1 \bmod N)}, y\_{(i+1 \bmod N)})$를 잇는 선분 $N$개의 합집합이다.

입력은 다음 제약을 만족한다.

• 입력의 모든 수는 정수이다.
• $3 \le N \le 100\,000$
• 모든 $0 \le i < N$에 대해 $0 \le x\_i \le 300\,000$이고 $0 \le y\_i \le 300\,000$이다.
• 모든 $0 \le i < j < N$에 대해 $x\_i \ne x\_j$ 또는 $y\_i \ne y\_j$이다.
• 입력은 단순 다각형 경계를 반시계 방향으로 따라가는 순서를 준다. 특히 이 다각형은 자기 자신과 교차하지 않는다.

출력은 다음 형식이다.

$M$

$z\_0$ $w\_0$

$z\_1$ $w\_1$

$\vdots$

$z\_{M-1}$ $w\_{M-1}$

최종 사용 가능한 마법진은 각 $0 \le i < M$에 대해 점 $(z\_i, w\_i)$와 $(z\_{(i+1 \bmod M)}, w\_{(i+1 \bmod M)})$를 잇는 선분 $M$개의 합집합이다.

출력은 다음 제약을 만족한다.

• 출력의 모든 수는 정수이다.
• 점 $(z\_0, w\_0)$은 모든 $1 \le i < M$에 대해 점 $(z\_i, w\_i)$보다 사전순으로 작다. 즉, ($z\_0 < z\_i$) 또는 ($z\_0 = z\_i$이고 $w\_0 < w\_i$)이다.
• 모든 $0 \le i < M$에 대해 $(z\_i, w\_i)$, $(z\_{(i+1 \bmod M)}, w\_{(i+1 \bmod M)})$, $(z\_{(i+2 \bmod M)}, w\_{(i+2 \bmod M)})$는 한 직선 위에 있지 않다.
• 출력은 볼록 다각형 경계를 반시계 방향으로 따라가는 순서이다.

위 제약을 만족하는 출력은 하나뿐임을 증명할 수 있다.

다음 그림은 첫 번째 예제의 처음 마법진이다.

다음 표는 마법진을 사용 가능하게 만들기 위해 도구를 쓰는 순서이다. 경계의 점선 부분은 도구가 수정한 경로이며, 수정 후에는 빨간 부분이 된다.

단계 0	단계 1
단계 2	단계 3
단계 4