문제

컨벡스 헐은 주어진 점들을 모두 포함하는 최소 넓이의 볼록 다각형을 의미한다.

점들의 집합이 주어졌을때 컨벡스헐을 구하라는 문제를 풀던 성현이는, 이 알고리즘이 너무 어려워 포기하고말았다 ㅜㅜ

그래서 성현이는 컨벡스 헐 대신 컨벡스 헐~ 을 정의했다.

컨벡스 헐~ 이란 모든 점을 포함하는 임의의 볼록다각형을 의미한다. 이때, 경계에 놓인 점들도 포함한다고 정의한다.

컨벡스 헐~ 은 주어진 점의 집합에 대하여 유일하지 않으며 여러 개 존재한다.

컨벡스 헐 문제를 해결하지 못해 슬픈 성현이를 위해 $N$개의 점이 주어질때 , 아무 컨벡스 헐~ 을 구해보자.

입력

첫째줄에 점들의 개수인 $N$ 이 주어진다. $(0 ≤ N ≤ 10^5)$

둘째줄에 점들의 $a$, $b$좌표가 공백을 사이에 두고 주어진다 $(0 ≤ a,b ≤ 10^9)$

출력

컨벡스 헐~ 을 구성하는 점들의 개수 $T$ 를 출력한다. $T$는 $(3 ≤ T ≤ 10^5)$ 를 만족해야하며, 해당범위 내에서 문제를 해결 할 수 있음이 보장된다.

이후 $T$개의 줄에 컨벡스 헐~을 이루는 점들을 임의의 순서대로 출력한다.

각각의 점들의 좌표 $x$, $y$는 $(0 ≤ x,y ≤ 10^9)$ 를 만족해야한다.

예제 입력 1

5
1 1 
1 2
2 3
4 2
3 0

예제 출력 1

5
0 1
0 2
2 4
5 2
3 0

힌트

노트

엄밀한 컨벡스헐의 수학적 정의는 위와같지 않다. 유클리드 공간에 있는 어떤 집합 $C$가 주어졌을 때, $C$ 안의 임의의 두 점을 연결하는 선분(Line segment) 상의 모든 점이 다시 $C$에 속한다면, 집합 $C$를 '볼록 집합'이라고 하며, 이를 수식으로 표현하면 다음과 같다.

$tx + (1-t)y \in C$

집합 $C$가 볼록 집합일 필요충분조건은 임의의 $x, y \in C$와 임의의 실수 $t \in [0, 1]$에 대하여 위와같은 식이 성립하는 것이다.

이때 컨벡스헐은 다음과 같이 정의된다.

$\text{Conv}(X) = \bigcap \{ C \mid X \subseteq C, C \text{ is a convex set} \}$

유클리드공간 이외에도 컨벡스헐이 정의될수있다. 아주 재미있으니 관심있다면 해석학을 들어보자. 본 내용은 문제풀이와 관련되어있지 않다.