CF690B3.Recover Polygon (hard)

Zombies have found out about the Zombie Contamination level checker and managed to damage it! Now detecting the shape of their main compound will be a real challenge for Heidi. As before, a lair can be represented as a strictly convex polygon on a lattice. Each vertex of the polygon occupies a point on the lattice. However, the damaged Zombie Contamination level checker can only tell, for each cell, whether the level of Zombie Contamination for that cell is in the set {1, 2, 3}. In other words, Heidi knows all the cells of the lattice for which the Contamination level is not 0 and not 4.

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

僵尸已经发现了“僵尸污染水平检测器”，并成功将其损坏！如今，要探测它们主基地的形状，对海蒂来说将是一项真正的挑战。与之前一样，巢穴可以表示为格点上的一个严格凸多边形，该多边形的每个顶点均位于格点上。然而，损坏后的僵尸污染水平检测器仅能对每个单元格报告其污染水平是否属于集合 $\{1,\,2,\,3\}$。换言之，海蒂仅知晓所有污染水平不为 $0$ 且不为 $4$ 的格点单元格。

基于这一信息，海蒂仍希望精确获知巢穴的形状，以便向僵尸降下毁灭。请帮助她！

The input contains multiple test cases.

The first line of each test case contains two space-separated integers N and M, where N is the size of the lattice grid (5 ≤ N ≤ 100000) and M is the number of lattice points for which the Zombie Contamination level is 1, 2, or 3 (8 ≤ M ≤ 200000).

The second line of each test case contains M pairs of integers _x_1, _y_1, ..., x__M, y__M – coordinates of the cells with Zombie Contamination level not equal to 0 nor 4. It is guaranteed that 1 ≤ x__i, y__i ≤ N. All pairs x__i, y__i are different.

Cells are enumerated based on the coordinates of their upper right corner. This means that the bottommost leftmost cell that touches the origin has coordinates (1, 1), and the uppermost leftmost cell is identified as (1, N).

The last line of the file contains two zeroes. This line should not be treated as a test case. The sum of the M values for all tests in one file will not exceed 200000.

输入包含多个测试用例。

每个测试用例的第一行包含两个以空格分隔的整数 $N$ 和 $M$，其中 $N$ 是晶格网格的大小（$5\leq N\leq 100000$），$M$ 是僵尸污染等级为 $1$、$2$ 或 $3$ 的晶格点个数（$8\leq M\leq 200000$）。

每个测试用例的第二行包含 $M$ 对整数 $x_1,\,y_1,\,...,\,x_M,\,y_M$ —— 表示污染等级不为 $0$ 且不为 $4$ 的单元格的坐标。保证对所有 $i$ 都有 $1\leq x_i,\,y_i\leq N$。所有坐标对 $(x_i,\,y_i)$ 互不相同。

单元格的编号基于其右上角顶点的坐标。这意味着：接触坐标原点的最左下角单元格的坐标为 $(1,\,1)$，而最左上角单元格的坐标为 $(1,\,N)$。

文件的最后一行包含两个零。该行不应被视作一个测试用例。单个输入文件中所有测试用例的 $M$ 值之和不超过 $200000$。

For each test case, the following output is expected:

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 1 and N - 1. A vertex (_x_1, _y_1) is lexicographically smaller than vertex (_x_2, _y_2) if _x_1 < _x_2 or .

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