← 返回题目列表

Codeforces · 690/B2

B2. 恢复多边形(中)

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

现在海蒂已经确保她的僵尸污染等级检查器正常工作,是时候出击了!这次,僵尸巢穴是晶格上严格的凸多边形。多边形的每个顶点占据晶格上的一个点。对于格子的每个单元格,海蒂都知道僵尸污染的程度——巢穴内部或边界上的单元角的数量。

有了这些信息,海蒂想知道巢穴的确切形状,以便对僵尸进行毁灭性打击。帮助她!

输入

输入包含多个测试用例。

每个测试用例的第一行包含一个整数N,即格子网格的大小(5 ≤ N ≤ 500)。接下来的 N 行每行包含 N 个字符,描述格子中每个单元格的僵尸污染级别。每行的每个字符都是 0 到 4 之间的数字。

单元格的排列顺序与上图所示的顺序相同:行按照 y 坐标值递减的顺序排列,在一行中单元格按照 x 坐标递增的顺序排列。这意味着第一行对应于坐标为 (1, N), ..., (N, N) 的单元格,最后一行对应于坐标为 (1, 1), ..., (N, 1) 的单元格。

文件的最后一行包含零。该行不应被视为测试用例。一个文件中所有测试的 N 值总和不会超过 5000。

输出

对于每个测试用例,给出以下输出:

输出的第一行应包含一个整数 V,即秘密巢穴的多边形的顶点数。接下来的 V 行每条应包含两个整数,从字典顺序最小的顶点开始按顺时针顺序表示多边形的顶点。

示例

输入 #1

8
00000000
00000110
00012210
01234200
02444200
01223200
00001100
00000000
5
00000
01210
02420
01210
00000
7
0000000
0122100
0134200
0013200
0002200
0001100
0000000
0

输出 #1

4
2 3
2 4
6 6
5 2
4
2 2
2 3
3 3
3 2
3
2 5
4 5
4 2

注意

保证解始终存在且唯一。保证在正确的解中,多边形顶点的坐标在 2 和 N - 2 之间。如果 x1 < x2 或 $$x_{1}=x_{2}\wedge y_{1}<y_{2}$$,则顶点 (x1, y1) 按字典顺序小于顶点 (x2, y2)。