시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 209 100 47 39.167%

문제

정수좌표를 갖는 점을 격자점이라고 한다. 격자 다각형은 모든 꼭지점이 격자점으로 이루어진 다각형이다.

만약, 다각형의 두 꼭지점을 잇는 모든 선분이 다각형 내부(또는 경계)에 있다면, 이 다각형을 볼록 다각형이라고 한다. 즉, 다각형의 내부각이 모두 180도 보다 작은 것이다.

격자점으로 이루어진 집합 S가 주어졌을 때, S의 모든 격자점을 포함하는 가장 작은 볼록 (격자) 다각형을 컨벡스 헐이라고 한다. 컨벡스 헐의 꼭지점은 모두 S에 포함된 격자점이어야 한다. 만약, 모든 점이 같은 일직선 상에 있다면, 컨벡스 헐은 선분이 될 것이다. (오른쪽 그림)

아래 그림에서 집합에 포함된 점은 굵은 점으로, 컨벡스 헐의 꼭지점은 X로, 변은 선분으로 나타낸 그림이다.

격자 다각형의 꼭지점의 일반적인 순서는 다음과 같다.

1. 첫번째 꼭지점은 y좌표가 가장 큰 점이다. 만약, 그러한 점이 2개라면, x가 작은 점이 첫번째 점이다.

2. 그 다음 점부터는 시계방향 순서이다.

격자점의 집합이 주어졌을 때, 컨벡스 헐을 일반적인 순서로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 P(1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 집합에 포함된 격자점의 수 N(3 ≤ N ≤ 50)이 주어진다. 나머지 줄은 집합에 포함되어 있는 격자점의 좌표가 한 줄에 5개씩 주어진다. (마지막 줄은 이보다 적을 수 있다) 모든 점은 x와 y좌표가 순서대로 주어지며, 공백으로 구분되어 있다.

출력

각 테스트 케이스에 대해서, 첫째 줄에는 컨벡스 헐에 포함된 점의 수를 출력한다. 그 다음 줄부터 컨벡스헐에 포함된 격자점을 한 줄에 하나씩 일반적인 순서대로 출한다. x와 y를 공백으로 구분하여 출력한다.

예제 입력

4
25
2 1 7 1 1 2 9 2 1 3
10 3 1 4 10 4 1 5 10 5
2 6 10 6 2 7 9 7 3 8
8 8 4 9 7 9 6 2 3 3
5 4 7 5 8 6 4 6 3 7
30
3 9 6 9 3 8 9 8 3 7
12 7 2 6 12 6 2 5 12 5
2 4 12 4 1 3 11 3 1 2
11 2 1 1 11 1 1 0 10 0
4 -1 10 -1 7 -2 10 -2 5 0
7 3 4 5 6 8 3 1 2 6
3
3 1 2 2 1 3
6
1 3 19 1 4 2 2 1 11 2
10 1

예제 출력

10
4 9
7 9
10 6
10 3
9 2
7 1
2 1
1 2
1 5
2 7
8
3 9
6 9
12 7
12 4
10 -2
7 -2
1 0
1 3
2
1 3
3 1
4
1 3
11 2
19 1
2 1

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest G번