항공 고고학

앤드루는 방학 동안 항공 고고학 조사팀에서 일한다. 이 팀은 핵 영상 분광법으로 선사 문화의 지하 유적을 조사한다. 오늘 앤드루가 맡은 일은 분광계를 실은 헬리콥터가 근처 저지대의 조사 구역 위를 지나도록 비행 경로를 정하는 것이다. 분광계는 민감하고 손상되기 쉬운 장비라서, 측정 잡음을 줄이려면 헬리콥터가 일정한 속도로 완전한 직선을 따라 날아야 한다.

저지대의 지표 아래에는 선사 시대 정착지가 여러 곳 묻혀 있다. 다른 방법으로 각 정착지의 위치와 경계를 이미 확정했고, 그 경계는 모두 앤드루가 쓸 수 있는 지도 한 장에 그려져 있다. 비행에서 되도록 많은 정착지 위를 지나야 하므로, 앤드루는 지도에 그려진 정착지를 가장 많이 지나는 직선을 찾아야 한다.

정착지의 모양은 복잡하고 서로 어지럽게 겹쳐 있어서, 직선을 어디에 그어야 하는지는 한눈에 보이지 않는다.

입력은 지도에 그려진 정착지의 모양과 위치를 설명한다. 각 정착지는 단순 다각형이다. 즉 인접하지 않은 두 경계 선분은 서로 닿지도 않고 교차하지도 않는다. 서로 다른 다각형은 겹칠 수 있다.

입력에는 여러 개의 테스트 케이스가 들어 있고, 파일이 끝나는 곳에서 입력도 끝난다. 각 테스트 케이스의 첫 줄에는 지도에 있는 다각형의 개수인 양의 정수 $N$이 주어진다. 이어서 $N$개의 다각형 정보가 주어진다. 각 다각형 정보의 첫 줄에는 다각형의 꼭짓점 개수인 정수 $M$ ($M \ge 3$)이 주어지고, 다음 $M$개의 줄에는 꼭짓점의 좌표 $x$와 $y$가 공백으로 구분되어 한 줄에 하나씩 주어진다. 꼭짓점은 다각형 경계를 따라 시계 방향으로 나열되어 있다. 모든 좌표는 절댓값이 $10000$ 이하인 정수다. 한 테스트 케이스에 있는 모든 다각형의 꼭짓점 개수의 합은 $1000$을 넘지 않는다.

각 테스트 케이스마다 직선 하나가 지날 수 있는 다각형의 최대 개수 $P$를 한 줄에 출력한다. 직선이 다각형의 내부와 만나는 경우만 센다. 직선이 다각형의 경계에만 닿고 내부의 어떤 점도 지나지 않으면 그 다각형은 지나지 않은 것으로 본다.