AT_tenka1_2012_final_d さんかく

平面上有 $N$ 个点，其中 $N$ 是 $3$ 的倍数。你的任务是使用这些点构造 $N/3$ 个三角形，使这些三角形的面积总和尽可能大。给定的第 $i$ 个点的坐标 $(x_i, y_i)$，其中 $0 \le x_i \le 100,000$ 和 $0 \le y_i \le 100,000$。 高桥君决定使用计算机来解决这个问题，但没能找到理想的算法，于是他采取了随机的方法。他随机选择三个点构成一个三角形，并重复这一过程 $N/3$ 次。经过一千万次这样的尝试，他选出了面积最大的结果。 你的目标是找到一个三角形的组合，使其面积总和不小于高桥君的最优结果。输入格式如下： > $N$ > $x_0$ $y_0$ > : > $x_{N-1}$ $y_{N-1}$ - 输入共有 $N+1$ 行。 - 第一行是一个整数 $N$（$3 \le N \le 3,000$），代表平面上的点数，且 $N$ 是 $3$ 的倍数。 - 接下来的每一行给出一个点的坐标 $(x_i, y_i)$，并保证 $x_i$ 和 $y_i$ 的范围在 $0 \le x_i, y_i \le 100,000$。 - 对任意两个不同的点 $(x_i, y_i)$ 和 $(x_j, y_j)$，保证至少有一维坐标不同，即 $x_i \ne x_j$ 或 $y_i \ne y_j$。 测试数据包含以下几种情况，对不同的 $N$ 值每种数据集给出的点数不同： - level1（每个 $2$ 分，共 $10$ 组）：$N=9$ - level2（每个 $2$ 分，共 $10$ 组）：$N=18$ - level3（每个 $2$ 分，共 $15$ 组）：$N=300$ - level4（每个 $2$ 分，共 $15$ 组）：$N=3,000$ 你需要输出一个三角形组合，其面积总和不小于高桥君的结果。每个三角形的顶点需在一行中输出，编号用空格分隔。无需关注三角形的输出顺序，或是每个三角形内顶点的顺序。每行的结尾需要换行。

无

无

- $3 \le N \le 3,000$ - $N$ 是 $3$ 的倍数。 - $0 \le x_i, y_i \le 100,000$ - 对于每对不同的点 $(x_i, y_i)$ 和 $(x_j, y_j)$，至少有一个坐标不同，即 $x_i \ne x_j$ 或 $y_i \ne y_j$。 **本翻译由 AI 自动生成**