CF690B2.Recover Polygon (medium)

Now that Heidi has made sure her Zombie Contamination level checker works, it's time to strike! This time, the zombie lair is a strictly convex polygon on the lattice. Each vertex of the polygon occupies a point on the lattice. For each cell of the lattice, Heidi knows the level of Zombie Contamination – the number of corners of the cell that are inside or on the border of the lair.

Given this information, Heidi wants to know the exact shape of the lair to rain destruction on the zombies. Help her!

在海蒂确认她的僵尸污染检测器正常工作后，是时候发起进攻了！这一次，僵尸巢穴是一个严格凸的格点多边形，其每个顶点均位于格点上。对于格点中的每一个单元格，海蒂已知其僵尸污染等级——即该单元格的四个角中，位于巢穴内部或边界上的角的个数。

根据这一信息，海蒂希望精确还原出巢穴的形状，以便向僵尸降下毁灭性的打击。请帮助她！

The input contains multiple test cases.

The first line of each test case contains one integer N, the size of the lattice grid (5 ≤ N ≤ 500). The next N lines each contain N characters, describing the level of Zombie Contamination of each cell in the lattice. Every character of every line is a digit between 0 and 4.

Cells are given in the same order as they are shown in the picture above: rows go in the decreasing value of y coordinate, and in one row cells go in the order of increasing x coordinate. This means that the first row corresponds to cells with coordinates (1, N), ..., (N, N) and the last row corresponds to cells with coordinates (1, 1), ..., (N, 1).

The last line of the file contains a zero. This line should not be treated as a test case. The sum of the N values for all tests in one file will not exceed 5000.

输入包含多个测试用例。

每个测试用例的第一行包含一个整数 $N$，表示格点网格的大小（$5 \leq N \leq 500$）。接下来的 $N$ 行，每行包含 $N$ 个字符，描述格点中每个单元格的僵尸污染等级。每行的每个字符均为介于 0 到 4 之间的数字。

单元格的给出顺序与上方图片中所示顺序一致：行按 $y$ 坐标递减的顺序排列；而在同一行中，单元格按 $x$ 坐标递增的顺序排列。这意味着第一行对应坐标为 $(1,\,N),\,\dots,\,(N,\,N)$ 的单元格，而最后一行对应坐标为 $(1,\,1),\,\dots,\,(N,\,1)$ 的单元格。

文件的最后一行包含一个数字 0。该行不应被视作一个测试用例。一个文件中所有测试用例的 $N$ 值之和不超过 5000。

For each test case, give the following output:

The first line of the output should contain one integer V, the number of vertices of the polygon that is the secret lair. The next V lines each should contain two integers, denoting the vertices of the polygon in the clockwise order, starting from the lexicographically smallest vertex.

对于每个测试用例，请输出以下内容：

输出的第一行应包含一个整数 $V$，表示作为秘密基地的多边形的顶点数。接下来的 $V$ 行每行应包含两个整数，按顺时针顺序给出该多边形的各个顶点，起始顶点为字典序最小的顶点。

It is guaranteed that the solution always exists and is unique. It is guaranteed that in the correct solution the coordinates of the polygon vertices are between 2 and N - 2. A vertex (_x_1, _y_1) is lexicographically smaller than vertex (_x_2, _y_2) if _x_1 < _x_2 or .

保证解一定存在且唯一。在正确解中，多边形顶点的坐标均介于 $2$ 与 $N-2$ 之间。顶点 $(x_1, y_1)$ 在字典序上小于顶点 $(x_2, y_2)$，当且仅当 $x_1 < x_2$ 或 。