격자점 볼록 껍질

정수 좌표를 갖는 점을 격자점이라고 한다. 모든 꼭짓점이 격자점인 다각형을 격자 다각형이라고 한다.

다각형의 임의의 두 점을 잇는 선분이 항상 다각형의 내부 또는 경계 위에 있다면, 그 다각형은 볼록 다각형이다. 다르게 말하면 모든 내부각이 180도보다 작다.

격자점으로 이루어진 집합 S가 주어진다. S의 모든 점을 포함하는 가장 작은 볼록 도형을 S의 볼록 껍질이라고 한다. 볼록 껍질의 꼭짓점은 모두 S에 포함된 격자점이어야 한다. 모든 점이 한 직선 위에 있으면 볼록 껍질은 선분이 된다.

아래 그림에서 집합에 포함된 점은 굵은 점, 볼록 껍질의 꼭짓점은 X, 볼록 껍질의 변은 선분으로 표시되어 있다.

격자 다각형의 꼭짓점은 다음의 표준 순서로 나열한다.

1. 첫 번째 꼭짓점은 y좌표가 가장 큰 점이다. 그런 점이 여러 개라면 x좌표가 가장 작은 점이 첫 번째 꼭짓점이다.
2. 그 다음 꼭짓점부터는 시계 방향 순서로 나열한다.

격자점 집합이 주어졌을 때, 그 집합의 볼록 껍질을 표준 순서로 출력하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 P가 주어진다. (1 <= P <= 1000)

각 테스트 케이스의 첫째 줄에는 집합에 포함된 격자점의 수 N이 주어진다. (3 <= N <= 50)

이후에는 집합에 포함된 격자점의 좌표가 주어진다. 각 좌표는 x, y 순서의 정수 쌍이며 공백으로 구분된다. 한 줄에는 좌표가 최대 5개까지 주어지고, 마지막 줄에는 더 적게 주어질 수 있다. 모든 좌표값의 절댓값은 20 이하이다.

각 테스트 케이스마다 먼저 볼록 껍질에 포함된 꼭짓점의 수를 한 줄에 출력한다.

그 다음 줄부터 볼록 껍질의 꼭짓점을 한 줄에 하나씩 표준 순서로 출력한다. 각 줄에는 x와 y를 공백으로 구분하여 출력한다.