Description

给定二维平面上的一个点集 $P$，包含 $\mathbf{N}$ 个互不相同的点。你需要找到一个最大的三角形集合满足以下条件：

• 集合中每个三角形的顶点都来自 $P$，且 $P$ 中的每个点最多作为一个三角形的一个顶点。
• 集合中的每个三角形面积必须为正（即三个顶点不共线）。
• 对于集合中任意两个三角形的边，它们的交集要么为空，要么是其中一条边的端点。
• 对于集合中任意两个三角形，它们内部区域的交集要么为空，要么完全等于其中一个三角形。

下图展示的三角形集合满足以上所有条件：

而下图中任意一对黄色和红色三角形的组合都不满足条件：

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后每个测试用例的第一行是一个整数 $\mathbf{N}$，接着 $\mathbf{N}$ 行，每行包含两个整数 $\mathbf{X}_i$ 和 $\mathbf{Y}_i$，表示第 $i$ 个点的坐标。

Output Format

对于每个测试用例，首先输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足条件的三角形集合的最大大小。然后输出 $y$ 行，每行三个整数 $p_j\ q_j\ r_j$，表示第 $j$ 个三角形由输入中的第 $p_j$、$q_j$ 和 $r_j$ 个点组成（点从 1 开始编号）。

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

Case #1: 3
3 4 5
1 7 9
6 2 8
Case #2: 2
2 3 1
6 5 4
Case #3: 0

Hint

样例解释

样例 #1 如下图所示。注意存在其他有效的构造方式也能达到最大三角形数量：

样例 #2 如下图所示。同样存在其他有效的构造方式能组成 2 个三角形：

样例 #3 中，所有给定点共线，因此无法组成有效的三角形。

限制条件

• $1 \leq \mathbf{T} \leq 100$
• $-10^9 \leq \mathbf{X}_i \leq 10^9$（所有 $i$）
• $-10^9 \leq \mathbf{Y}_i \leq 10^9$（所有 $i$）
• 所有点的坐标互不相同

测试集 1（8 分，可见判定）

• $3 \leq \mathbf{N} \leq 12$

测试集 2（42 分，隐藏判定）

• $3 \leq \mathbf{N} \leq 3000$

翻译由 DeepSeek V3 完成