问题描述

本题包含 $T$ 组测试用例。

给定 $N$ 个二维点 $(x_i, y_i)$（$0 \le i \le N-1$），令 $P$ 为其凸包。请按逆时针顺序输出 $P$ 的顶点坐标。

如需更详细的定义，请参见以下说明。

注意：

• 对于一个（多重）二维点集 $S$，记其凸包为 $\operatorname{conv}(S)$。
• 定义 $P = \operatorname{conv}(\{(x_i, y_i) \mid 0 \le i \le N-1\})$。
• 我们可以证明存在一个最小集合 $S'$ 满足 $\operatorname{conv}(S') = P$；$P$ 的顶点即定义为 $S'$ 中的元素。
• 当 $|S'| \le 2$ 时，可任意输出 $S'$ 中的点；当 $|S'| \ge 3$ 时，可证明 $P$ 是一个凸多边形，且 $S'$ 即为其顶点，此时可定义其逆时针顺序；允许旋转该顺序，只要为逆时针即可。
• 根据上述定义，不应输出 $S$ 中位于 $P$ 边上但非顶点的点。
• 输入可能包含多个坐标相同的点，但输出中不应包含重复坐标点。

约束条件

• $1 \le T \le 10^5$
• $0 \le N \le 5 \times 10^5$
• $|x_i|, |y_i| \le 10^9$
• $x_i, y_i$ 为整数。
• 所有测试用例中 $N$ 的总和不超过 $5 \times 10^5$

输入

T
N
x₀ y₀
x₁ y₁
:
x_{N-1} y_{N-1}
N
x₀ y₀
x₁ y₁
:
x_{N-1} y_{N-1}
:

输出

对每组测试用例，按如下格式输出坐标：

M
x₀' y₀'
x₁' y₁'
:
x_{M-1}' y_{M-1}'

1
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

4
0 0
2 0
2 2
0 2

4
0
1
1 1
3
1 1
1 1
1 1
4
-2 -2
-1 -1
0 0
0 0

0
1
1 1
1
1 1
2
-2 -2
0 0