웨비 지하철
시간 제한8초메모리 제한512 MB
여러 개의 꺾은선 지하철 노선이 주어질 때, 같은 층에 놓인 노선의 선분이 서로 교차하거나 접촉하지 않도록 배치하는 최소 층수를 구한다.
문제
당신은 오이콧시 국토교통국 소속 공무원이다. 국토교통국은 오이콧 도심에 지하철망을 건설할 계획을 세웠다.
계획에는 n개의 지하철 노선이 지어지며, 각 노선에는 두 개 이상의 역이 있다. 기술적인 문제로 인해 두 역 사이의 선로는 곧아야 하고 기울기가 없어야 한다. 게다가 선로는 역 위에서조차 다른 선로와 접촉할 수 없다. 즉, 같은 층에 있는 두 지하철은 교차점을 가질 수 없다.
당신의 임무는 계획에 필요한 최소 층수를 구하는 것이다.
입력
입력은 여러 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다:
N
Line1
Line2
...
LineN
여기서 N은 계획에서 지어질 지하철 노선의 수를 나타내는 양의 정수이고(N ≤ 22), Linei는 i번째 지하철 노선의 설명으로 형식은 다음과 같다:
S
X1 Y1
X2 Y2
...
XS YS
S는 노선에 있는 역의 수를 나타내는 양의 정수이고(S ≤ 30), (Xi, Yi)는 노선의 i번째 역 좌표를 나타낸다(-10000 ≤ Xi, Yi ≤ 10000). 선로는 설명에서 연속한 두 역 사이에 지어진다. 같은 노선의 역 중 좌표가 같은 역은 없다.
입력은 N = 0인 데이터셋으로 끝나며, 이 데이터셋은 처리하지 않는다.
출력
각 데이터셋마다 필요한 최소 층수를 출력한다.