공룡 발자국
시간 제한2초메모리 제한512 MB
N개의 점이 주어질 때, 유일한 최남단 점을 발뒤꿈치로 하고 좌회전과 우회전이 번갈아 나타나며 발가락 선분이 다각형 안에 있고 골을 지나지 않는 조건을 만족하는 발자국 중 발가락이 가장 많은 것을 찾는다. 가장 남쪽 점에서 시작해 반시계 방향으로 정렬한 점들 가운데, 각도 순서를 유지하면서 좌회전과 우회전이 교대로 나타나는 최장 부분수열을 구하는 문제로 바꿀 수 있다. 부분수열의 길이가 홀수여야 발가락이 정수 개가 되고, 마지막 점에서 발뒤꿈치로 돌아올 때의 회전 방향과 골을 지나지 않는 조건도 확인해야 한다. 서브태스크에 따라 N이 커지므로, 회전 방향을 기준으로 나눈 두 개의 최장 증가 부분수열을 O(N log N)에 계산하고, 발가락 선분이 다각형을 벗어나거나 골을 지나지 않는지 기하학적으로 검사하는 과정이 필요하다. 좌표 범위는 -10^8 이상 10^8 이하이고, 모든 점은 서로 다르며 y좌표가 가장 작은 점이 유일하다. 정답이 여러 개면 아무거나 출력하고, 발자국이 존재하지 않으면 0을 출력한다.
문제
고대 공룡들이 남쪽에서 북쪽 방향으로 걸어간 발자국들이 발견되었다. 아래 그림은 발견된 공룡 발자국들의 다양한 예이다.
발자국을 분석한 결과 모든 발자국은 하나의 발뒤꿈치와 k개의 발가락 (k ≥ 2)을 가지며, 두 발가락 사이마다 골이 존재한다. 이를 바탕으로 위 그림의 발자국을 단순화시켜보면 아래와 같이 2k각형으로 표현이 된다.
발자국의 다각형에서 발뒤꿈치를 시작으로 반시계 방향으로 돌면 항상 첫 번째 발가락에서 좌회전, 첫 번째 골에서 우회전, 두 번째 발가락에서 좌회전, 두 번째 골에서 우회전, ……, k-1번째 골에서 우회전, k번째 발가락에서 좌회전해서 발뒤꿈치로 돌아오게 된다. 또한 발뒤꿈치와 발가락을 선분으로 잇는 경우 다음 조건을 항상 만족한다.
- 해당 선분은 발자국의 다각형을 벗어나지 않는다.
- 해당 선분은 골을 지나지 않는다.
다음 그림은 발자국이 될 수 없는 다각형들의 예이다.
 |  |
| 조건 1 위배 | 조건 2 위배 |
발자국이 발견된 일부 지역에서는 불행히도 정확한 발자국이 남아있지 않고 발자국 다각형의 꼭짓점이 될 수 있는 점들만 남아있다. 심지어 여기에는 발자국과 관련 없는 점들도 같이 남아있을 수 있다. 각 점의 위치는 좌표 (x, y)로 표현되며, x값은 서쪽에서 동쪽으로 증가하고 y값은 남쪽에서 북쪽으로 증가한다. 다행히도 점들 중 가장 남쪽에 있는 점은 유일하며 발뒤꿈치가 된다. 다음 그림의 예에서 보면 (20, 5) 점(붉은 점)이 가장 남쪽에 위치하므로 발뒤꿈치이다.
주어진 점들로 만들 수 있는 가장 많은 발가락을 가진 발자국을 찾고 싶다. 아래는 위 그림에서 찾은 가장 많은 발가락을 가진 발자국의 한 예이다.
점들의 좌표를 입력으로 받아서, 가장 많은 발가락을 가진 발자국을 하나 찾은 뒤 찾은 다각형의 꼭짓점의 개수와 각 꼭짓점의 좌표를 출력하는 프로그램을 작성하라.
입력
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 점의 수를 나타내는 정수 N이 주어진다. 다음 N개의 각 줄에는 한 점의 x좌표와 y좌표를 나타내는 두 정수가 주어진다. 입력으로 주어진 점들은 모두 서로 다르다는 것이 보장되고, y좌표가 가장 작은 점이 유일하다는 것도 보장된다.
출력
표준 출력으로, 첫 번째 줄에는 가장 많은 발가락을 가진 발자국 다각형의 꼭짓점의 개수 T를 출력한다. 다음 T개의 각 줄에는 발뒤꿈치부터 시작하여 반시계 방향으로 돌면서 각 꼭짓점의 x좌표와 y좌표를 출력한다. 그러한 발자국이 여러 개가 있다면 그 중 하나의 발자국만 출력한다. 발자국이 존재할 수 없는 경우 0을 출력한다.
제한
모든 서브태스크에서 -108 ≤ x, y ≤ 108 이다.