← 返回题目列表

AtCoder · icpc2014autumn_i

I. 为地图极限着色

中文机器翻译题面 查看原题

问题陈述

你刚刚转移到另一个世界,并获得了这个世界的地图。 这个世界上有好几个国家。 每个国家都有相连的领土, 它在地图上绘制为一个简单的多边形,由 $2$ 维平面中的边界段组成。

你对这个世界很陌生,所以你想在地图上画出国家来区分它们。 如果将相邻的国家涂成相同的颜色,则很难区分国家。 因此,你想给相邻的国家涂上不同的颜色。 在这里,如果两个国家的边界​​至少有一个长度严格大于 $0$ 的共同线段,我们定义两个国家相邻。 请注意,如果边界仅在点处接触,则两个国家不被视为相邻。

因为你没有这个世界的货币,所以你很难准备很多颜色。 绘制地图时最少需要多少种颜色才能使相邻国家可以涂上不同的颜色?


输入

输入由多个数据集组成。数据集数量不超过 35 美元。

每个数据集的格式如下。

$n$
$m_1$
$x_{1,1}$ $y_{1,1}$
:
:
$x_{1,m_1}$ $y_{1,m_1}$
:
:
$m_n$
$x_{n,1}$ $y_{n,1}$
:
:
$x_{n,m_n}$ $y_{n,m_n}$

每个数据集的第一行包含一个整数 $n$ ($1 \le n \le 35$), 它表示这个世界上的国家数量。

每个数据集的其余部分描述了代表国家的$n$个多边形的信息。 第$i$个多边形的信息第一行包含一个整数$m_i$($3\le m_i\le 50$),表示顶点数。 以下 $m_i$ 行按逆时针顺序描述顶点的坐标。 其中第 $j$ 行包含两个整数 $x_{i,j}$ 和 $y_{i,j}$ ($|x_{i,j}|, |y_{i,j}| \le 10^3$), 表示第 $i$ 个多边形的第 $j$ 个顶点的坐标。

您可以做出以下假设。

  • 每个多边形的面积均大于 $0$。
  • 同一多边形的两个顶点具有不同的坐标。
  • 同一多边形的两条线段没有任何公共点,除非两条线段在每个顶点相交。
  • 两个多边形没有公共区域。

输入结束由包含单个零的行表示。

输出

对于每个数据集,输出绘制地图的最小颜色数,以便相邻国家在一条线上涂上不同的颜色。


示例输入

1
3
0 0
1 0
0 1
4
4
0 0
10 0
10 10
0 10
4
10 0
20 0
20 10
10 10
4
0 10
10 10
10 20
0 20
4
10 10
20 10
20 20
10 20
3
4
-10 -10
2 2
10 10
-11 7
3
-1 -1
1 -1
0 0
3
0 0
3 -3
20 20
7
4
46 12
52 12
53 15
45 15
32
67 1
70 0
73 1
77 3
79 5
80 8
77 8
76 5
74 4
71 3
70 3
67 4
65 6
63 8
62 14
64 19
66 21
70 22
75 21
78 16
80 16
80 17
79 20
78 22
74 24
67 24
63 22
61 19
60 15
60 10
62 5
64 3
5
74 14
80 14
80 16
78 16
74 16
19
34 0
37 0
37 19
36 22
35 23
32 24
30 24
27 24
25 23
23 20
23 18
23 15
26 15
26 18
27 20
29 21
32 21
34 20
34 18
4
47 0
50 0
42 24
39 24
4
79 20
80 17
80 22
78 22
4
50 0
58 24
56 24
49 3
4
10
34 21
34 14
35 14
35 19
40 19
40 20
35 20
35 22
30 22
30 21
16
20 24
21 24
21 33
42 33
42 20
40 20
40 19
45 19
45 5
40 5
40 4
46 4
46 20
43 20
43 34
20 34
10
26 21
26 14
27 14
27 21
30 21
30 22
21 22
21 24
20 24
20 21
12
34 8
34 4
40 4
40 5
35 5
35 14
34 14
34 9
27 9
27 14
26 14
26 8
0

样本输入的输出

1
2
3
3
4