← 返回题目列表

Codeforces · 2215/E

E. 星图

中文机器翻译题面 查看原题

Funni酱喜欢看星星。

天空中有$$$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$$$-s 成对不同,并且所有 $$$y_i$$$-s 成对不同。

保证所有测试用例的 $$$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$$$ 个三角形的三颗星的索引。

示例

输入
复制

2
8
-10 1
-2 6
5 10
8 -9
-1 -2
3 0
0 3
1 -8
8
8 8
-5 3
-4 1
5 7
10 10
-3 5
-8 -10
-7 -1

输出
复制

8
6 5 8
6 8 4
1 6 5
7 1 6
2 7 1
3 2 7
3 7 6
3 6 4
2
2 3 8
6 2 3

注意

示例的第一个测试用例如下图所示:

示例的第二个测试用例如下所示: