Description

你最近购置了一块漂亮又宽阔的农场，现在你想围起一圈篱笆。你的农场里已经有 $N$ 根篱笆桩。

你将会用直线段连接这些篱笆桩，形成篱笆。不幸的是，出于你并不完全理解的法律原因，你的律师坚持认为你必须用上所有的篱笆桩，否则会有麻烦。

在本题中，篱笆桩用平面上的点表示。你需要以某种顺序排列这些篱笆桩，然后依次连接第一个和第二个、第二个和第三个，最后将最后一个和第一个相连。你构建的篱笆段需要组成一个无自交的多边形。也就是说，每个篱笆桩只连接两段篱笆，且在其他任何点上都至多有一段篱笆通过。

做到这一步很容易，但你还希望尽可能保留农场的宽阔。你可不希望大部分农场被篱笆圈在外面。因此，你希望构建的篱笆所围成的面积，要大于你可以只用一部分桩时能围成的最大面积的一半。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据第一行为篱笆桩数量 $N$，桩编号为 $0$ 到 $N-1$。接下来 $N$ 行，每行两个整数 $X_i$ 和 $Y_i$，用一个空格分隔，表示第 $i$ 个桩的坐标。

Output Format

对于每个测试用例，输出一行 "Case #x: "，其中 $x$ 为测试用例编号（从 $1$ 开始），后接 $N$ 个 $0$ 到 $N-1$ 之间的互不相同的整数，用空格分隔。它们是你围篱笆时依次经过的桩的编号（顺时针或逆时针均可），首尾相连。

如果有多种方案，输出任意一种即可。

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

Case #1: 0 1 2 3
Case #2: 0 1 4 2 3
Case #3: 0 2 1

Hint

样例说明

第一个测试用例中，共有三种可以构成的多边形，其中两种面积足够大，分别是序列 0 1 2 3 和 0 2 1 3。序列 0 1 3 2 对应的多边形面积太小。第二个测试用例中，必须保证多边形不自交，例如 0 1 2 3 4 或 0 1 3 4 2 都是不合法的。第三个测试用例中，任意顺序都能得到同一个三角形，都是合法的。

限制条件

• 所有桩的位置互不相同，且不会全部共线。

小数据集（9 分，测试集 1 - 可见）

• 时间限制：30 3 秒
• $1 \leq T \leq 100$
• $3 \leq N \leq 10$
• $-100 \leq X_i, Y_i \leq 100$

大数据集（13 分，测试集 2 - 隐藏）

• 时间限制：60 6 秒
• $1 \leq T \leq 30$
• $3 \leq N \leq 1000$
• $-50000 \leq X_i, Y_i \leq 50000$

翻译由 ChatGPT-4.1 完成。