现在海蒂已经确保她的僵尸污染等级检查器正常工作,是时候出击了!这次,僵尸巢穴是晶格上严格的凸多边形。多边形的每个顶点占据晶格上的一个点。对于格子的每个单元格,海蒂都知道僵尸污染的程度——巢穴内部或边界上的单元角的数量。
有了这些信息,海蒂想知道巢穴的确切形状,以便对僵尸进行毁灭性打击。帮助她!
输入
输入包含多个测试用例。
每个测试用例的第一行包含一个整数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)。