输入文件

题目类型说明

这是一道提交答案题。你需要针对题目给出的所有测试数据，构造输出文件并打包提交。

---

题目描述

给定 N 个平面上的点，点的坐标均为整数，且任意三点不共线。这些点是从正方形区域 [0, 10^9] × [0, 10^9] 中随机生成的。

你可以在这些点之间连接若干条线段，但要求：

• 任意两条你画出的线段，不能在内部相交；
• 不过它们可以有公共端点。

你的目标是在满足上述条件的前提下，连接这些点，使得由这些线段作为边所形成的不同三角形数量尽可能多。

两个三角形如果至少有一个顶点不同，就认为它们不同。

---

输入格式

第一行输入一个整数 N。

接下来 N 行，每行输入两个整数 X_i、Y_i，表示第 i 个点的坐标。

---

输出格式

第一行输出一个整数 M，表示你画出的线段条数，要求：

• M <= 5 × 10^5

接下来 M 行，每行输出两个不同的整数 i、j，表示连接第 i 个点和第 j 个点的一条线段。

要求：

• 点的编号按照输入顺序从 1 开始；
• 不能重复连接同一对点；
• 输出边的顺序无关；
• 每条边中两个端点的输出顺序也无关。

然后在第 M+2 行输出一个整数 K，表示你构造出的三角形个数。

接下来 K 行，每行输出三个不同的整数 p、q、l，表示一个三角形的三个顶点编号。

要求：

• 对于输出的每个三角形，这三对点之间都必须已经被你输出为线段；
• 同一个三角形不能重复输出；
• 三角形输出顺序无关；
• 每个三角形内部三个顶点的顺序也无关。

---

数据范围

• 0 <= N <= 50000
• 0 <= X_i, Y_i <= 10^9

并且保证：

• 任意三点不共线；
• 点是随机生成的。

---

测试方式

题目已经提供了全部 10 个测试点。你需要为每个测试点生成对应的输出文件。

对每个测试，你需要生成一个文本文件，内容即为该测试的输出答案。

---

提交方式

你提交到系统上的应是一个 ZIP 压缩包，压缩包中至少包含一个输出文件。

输出文件名必须形如：

triangles.xx.out

其中 xx 是测试编号；对于 1 到 9 号测试，需要补前导零，例如：

• triangles.01.out
• triangles.02.out
• ...
• triangles.10.out

每次上传一个 ZIP 压缩包，视为一次提交。

---

评分方式

如果某个测试中，你的输出出现以下任一情况，则该测试得分为 0：

• 输出格式非法；
• 输出的线段数超过 5 × 10^5；
• 有两条输出线段在内部相交；
• 输出的某个三角形并未真正由你输出的线段构成。

否则，该测试的得分计算公式为：

$$10 \times \min\left(\frac{\text{yours}}{\text{author}}, 1.0\right)^{1.12}$$

其中：

• author 表示该测试上作者解构造出的三角形数量；
• yours 表示你的输出中构造出的三角形数量。

---

作者解在各测试点的结果

测试编号	N	作者解构造出的三角形数
1	50	130
2	500	1470
3	1000	2970
4		2960
5	5000	14950
6		14940
7	25000	74954
8		74944
9	50000	149944
10

---

样例

输入

4
4 1
1 4
6 7
3 4

输出

6
1 2
2 3
1 3
1 4
2 4
4 3
4
1 3 2
1 2 4
3 1 4
2 4 3

样例解释

请注意：样例中的若干线段虽然有公共端点，但任意两条线段都不会在内部相交。