시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 136 36 27 34.177%

문제

한려해상국립공원은 한반도의 남쪽에 있으며, 120km에 걸친 독특한 해양 생태계를 가지고 있다. 공원은 360개 이상의 섬으로 이루어져 있으며, 섬의 크기도 모두 제각각 다르다. 69개의 무인도와 30개의 유인도로 이루어진 아름다운 수로는 바다의 보석과 같다는 찬사를 받는다.

공원 관리자 김상근은 등고선을 이용해 공원 내의 모든 섬의 고도를 조사하려고 한다. 등고선은 해발 고도가 같은 지점을 연결한 곡선이며, 볼록한 닫힌 곡선이다. (그림 1)

한려해상국립공원의 섬을 나타내는 등고선은 서로 겹치지 않으며, 타원과 같은 단순 볼록 곡선이며 닫혀있다. 

컴퓨터는 등고선 지도를 디지털 등고선 지도로 변형해서 사용한다. 디지털 등고선 지도의 등고선은 볼록 직교 다각형 (그림 2) 이다. 직교 다각형이란 모든 변이 수직 또는 수평인 다각형이다. 직교 다각형 P가 볼록이 되려면, P의 모든 내부와 수직선 또는 수평선과의 교점이 비어있거나 선분이어야 한다.

가장 바깥에 있는 등고선은 레벨 1이다. 등고선 c를 둘러싼 등고선의 레벨이 k인 경우에 c의 레벨은 k+1이다. 그림 2에의 지도에서 가장 높은 등고선의 레벨은 5이다.

등고선 n개로 이루어진 디지털 등고선 지도가 주어진다. 이 때, 가장 높은 등고선의 레벨을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 등고선의 개수 m(1 ≤ m ≤ 20,000)이 주어진다. 다음 m개 줄에는 각 등고선의 정보를 나타내는 2k+1개의 정수 k, x1, y1, x2, y2, ..., xk, yk (4 ≤ k ≤ 100, 1 ≤ xi, yi ≤ 109) 가 주어진다. k는 볼록 직교 다각형 Q의 꼭지점의 개수를 나타내며, (xi, yi)는 Q의 꼭지점을 나타낸다. 꼭지점은 반시계방향으로 주어진다. 두 볼록 직교 다각형이 겹치는 경우는 없다.

출력

각 테스트 케이스마다 가장 높은 등고선의 레벨을 출력한다.

예제 입력

2
5
4 5 3 14 3 14 12 5 12
4 6 4 13 4 13 11 6 11
4 7 5 12 5 12 10 7 10
4 8 6 11 6 11 9 8 9
4 9 7 10 7 10 8 9 8
4
4 10 7 11 7 11 8 10 8
6 3 7 5 7 5 9 6 9 6 12 3 12
6 8 5 9 5 9 6 12 6 12 9 8 9 
10 9 2 9 3 14 3 14 11 7 11 7 8 6 8 6 4 4 4 4 2

예제 출력

5
3

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2012 B번