17244 | 정적 볼록 껍질

이 문제에는 $T$ 개의 테스트 케이스가 있다.

$N$ 개의 2차원 점 $(x _ i , y _ i)$ ( $0\leq i\leq N - 1$ )가 주어질 때, $P$ 를 이 점들의 볼록 껍질이라고 하자. $P$ 의 정점 좌표를 반시계 방향 순서로 출력한다.

더 자세한 정의는 다음 참고를 확인한다.

참고:

2차원 점의 (다중)집합 $S$ 에 대해, $S$ 의 볼록 껍질을 $\mathrm{conv}(S)$ 로 표기한다.
$P$ 를 $P=\mathrm{conv}(\lbrace (x _ i, y _ i) \mid 0\leq i\leq N - 1\rbrace)$ 로 정의한다.
$\mathrm{conv}(S')=P$ 를 만족하는 최소 집합 $S'$ 가 존재함을 증명할 수 있다. $P$ 의 정점은 $S'$ 의 원소로 정의한다.
$|S'|\leq 2$ 일 때, $S'$ 의 점들을 임의의 순서로 출력한다. $|S'|\geq 3$ 일 때, $P$ 이 볼록 다각형이고 $S'$ 이 그 정점임을 증명할 수 있으며, 그 반시계 방향 순서를 정의할 수 있다. 이 순서를 회전할 수 있으며, 반시계 방향이기만 하면 어느 것이든 허용된다.
위 정의에 따라, $S$ 의 점이 $P$ 의 간선 위에 있더라도 정점이 아니라면 출력해서는 안 된다.
입력에는 좌표가 같은 점이 여러 개 포함될 수 있지만, 출력에는 좌표가 같은 점이 여러 개 포함되어서는 안 된다.

$T$
$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
$\vdots$

각 테스트 케이스마다 다음 형식으로 좌표를 출력한다.

$M$
$x'_0$ $y'_0$
$x'_1$ $y'_1$
:
$x'_{M - 1}$ $y'_{M - 1}$

정적 볼록 껍질