지도 색칠하기 익스트림
시간 제한8초메모리 제한512 MB
각 나라를 나타내는 단순 다각형이 주어질 때 양의 길이를 가진 변을 공유하면 인접하다고 보고, 인접 그래프의 색칠수 최솟값을 구한다.
문제
다른 세계로 넘어온 당신은 그 세계의 지도를 한 장 얻었다. 이 세계에는 여러 나라가 있다. 각 나라의 영토는 하나로 이어져 있고, 지도에는 국경선으로 둘러싸인 2차원 평면 위의 단순 다각형으로 그려져 있다.
이 세계가 낯선 당신은 나라를 구분하려고 지도에 색을 칠하려 한다. 인접한 두 나라를 같은 색으로 칠하면 구분하기 어려우니, 인접한 나라는 서로 다른 색으로 칠하려 한다. 여기서 두 나라의 국경선에 길이가 0보다 큰 공통 선분이 하나라도 있으면 두 나라가 인접하다고 정의한다. 국경선이 점에서만 닿는 두 나라는 인접하지 않다.
이 세계의 화폐가 없어서 색을 많이 준비하기는 어렵다. 인접한 나라를 서로 다른 색으로 칠하려면 색이 최소 몇 개 필요한가?
입력
입력은 여러 개의 데이터 세트로 이루어진다. 데이터 세트의 개수는 35개 이하이다.
각 데이터 세트의 형식은 다음과 같다.
n
m1
x1,1 y1,1
:
:
x1,m1 y1,m1
:
:
mn
xn,1 yn,1
:
:
xn,mn yn,mn
각 데이터 세트의 첫 줄에는 이 세계의 나라 수를 나타내는 정수 ()이 주어진다.
그다음에는 개 나라를 나타내는 다각형 정보가 이어진다. 번째 다각형 정보의 첫 줄에는 꼭짓점 수를 나타내는 정수 ()가 주어진다. 이어지는 개 줄에는 꼭짓점의 좌표가 반시계 방향 순서로 주어진다. 그중 번째 줄에는 번째 다각형의 번째 꼭짓점 좌표를 나타내는 두 정수 와 ()가 주어진다.
다음은 가정해도 된다.
- 각 다각형의 넓이는 0보다 크다.
- 같은 다각형의 두 꼭짓점은 좌표가 서로 다르다.
- 같은 다각형의 두 선분은 각 꼭짓점에서 정확히 두 선분이 만나는 경우를 빼면 공통점이 없다.
- 두 다각형이 겹치는 넓이는 없다.
입력의 끝은 0 하나만 있는 줄로 표시한다.
출력
각 데이터 세트마다 인접한 나라를 서로 다른 색으로 칠할 때 필요한 색의 최소 개수를 한 줄에 출력한다.