题目描述

译自 CCO 2025 Day2 T2「Patrol Robot」。

坐标控制组织开发了一款自主机器人，用于巡逻二维平面上的 $N$ 个重要地点。第 $i$ 个地点的坐标为 $(x_{i}, y_{i})$，且保证任意三个地点不在同一直线上。

为了帮助引导机器人，你可以在地面上绘制一些线段。每条线段必须直接连接两个重要地点，且任意两条线段不得相交，除非在端点处相交。

机器人将从任意线段的中点开始巡逻，面向其中一个端点。它将按照以下程序无限移动：

• 只要机器人位于线段的内部，它将向前移动，朝向线段的一个端点。
• 当机器人到达一个重要地点时，它最初会面向刚经过的线段的反方向。机器人将向右/顺时针转动，直到它的视线与离开当前位置的某条线段对齐。然后，机器人将开始沿这条新线段移动。

你的任务是绘制线段，使得无论机器人从何处开始，它都能保证无限多次访问每个重要地点。可以证明，这总是可能的。

输入格式

第一行包含一个整数 $N$ $(2 \leq N \leq 2000)$，表示重要地点的数量。

接下来的 $N$ 行，每行包含两个用空格分隔的整数 $x_{i}$ 和 $y_{i}$ $(-10^{9} \leq x_{i}, y_{i} \leq 10^{9})$，表示第 $i$ 个重要地点的坐标。

保证所有 $N$ 个重要地点都是不同的，且任意三个地点不在同一直线上。

输出格式

第一行输出一个正整数 $M$，表示你在地面上绘制的线段数量。

接下来的 $M$ 行，每行包含两个用空格分隔的整数 $u_{i}$ 和 $v_{i}$ $(1 \leq u_{i}, v_{i} \leq N, u_{i} \neq v_{i})$，表示你在第 $u_{i}$ 个和第 $v_{i}$ 个重要地点之间绘制了一条线段。

如果有多种正确的答案，输出其中任意一个即可。

4
0 0
1 1
1 2
2 1

3
1 2
2 3
2 4

重要地点和绘制的线段如下图所示：

无论机器人从何处开始，它都会无限多次访问每个重要地点。例如，如果机器人从地点 $1$ 和 $2$ 之间的线段中点开始，面向地点 $2$，则机器人访问的地点顺序为：

$$\underline{2, 4, 2, 3, 2, 1}, 2, 4, \dots,$$

其中下划线部分将无限重复。

8
0 0
0 3
1 1
1 2
4 1
4 2
5 0
5 3

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

重要地点和绘制的线段如下图所示：

无论机器人从何处开始，它都会无限多次访问每个重要地点。例如，如果机器人从地点 $4$ 和 $5$ 之间的线段中点开始，面向地点 $5$，则机器人访问的地点顺序为：

$$5, \underline{7, 5, 6, 5, 1, 2, 4, 3, 4, 8}, 7, 5, \dots, $$

其中下划线部分将无限重复。请注意，并不需要每条线段都被无限多次经过；只要每个地点被无限多次访问，解决方案就是合法的。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$8$	$2 \leq N \leq 4$
$2$	$16$	$2 \leq N \leq 8$
$3$	$12$	$3 \leq N$ 且 $N$ 个点按某种顺序构成凸多边形的顶点
$4$	$28$	$N$ 个点形成一个有 $N-1$ 个顶点的凸多边形，外加一个内部点
$5$	$36$	无