CF2215E Star Map

Funni-chan 喜欢观星。 天空中有 $n$ 颗星星，可以看作在平面直角坐标系上的点。第 $i$ 颗星星的坐标为 $(x_i, y_i)$。保证所有 $x_1, x_2, \ldots, x_n$ 互不相同，所有 $y_1, y_2, \ldots, y_n$ 也互不相同。星星以输入顺序从 $1$ 到 $n$ 编号。 Funni-chan 想要将这些星星两两相连，构成一个星座。 她定义星座的基本单位为由三颗星星两两连线组成的三角形。如果存在一个与坐标轴平行的矩形，使得三角形的三个顶点都在这个矩形的边界上，则称这样的三角形为和谐三角形。 Funni-chan 对星座提出了如下限制： - 星座中的每一个三角形都必须是和谐三角形。 - 星座中任意两个三角形的内部不能有公共部分。注意，三角形的边界不属于其内部。 在这些限制下，Funni-chan 希望她的星座中包含尽可能多的三角形。你的任务是求出这个最大数量，并构造出满足要求的星座方案。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 2\cdot 10^4$），表示测试用例的数量。 每个测试用例第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）——星星的数量。 接下来的 $n$ 行每行包含两个整数 $x_i$ 和 $y_i$（$-10^9\le x_i, y_i \le 10^9$）——第 $i$ 颗星星的坐标。保证所有 $x_i$ 互不相同，所有 $y_i$ 互不相同。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

每个测试用例输出两部分。 第一行输出一个整数 $m$（$0\le m\le 2\cdot n$），表示星座中最多能包含的三角形数量。 接下来的 $m$ 行，每行输出三个不同的正整数 $a_i, b_i, c_i$（$1 \le a_i, b_i, c_i \le n$），表示第 $i$ 个三角形所用的三颗星星的编号。

示例第一个测试用例的示意图如下：  示例第二个测试用例的示意图如下：  由 ChatGPT 5 翻译