P13299 [GCJ 2013 #3] Rural Planning [Unverified]

本题测试数据疑似有误，答案疑似出现了多边形自交的情况。

你最近购置了一块漂亮又宽阔的农场，现在你想围起一圈篱笆。你的农场里已经有 $N$ 根篱笆桩。 你将会用直线段连接这些篱笆桩，形成篱笆。不幸的是，出于你并不完全理解的法律原因，你的律师坚持认为你**必须用上所有的篱笆桩**，否则会有麻烦。 在本题中，篱笆桩用平面上的点表示。你需要以某种顺序排列这些篱笆桩，然后依次连接第一个和第二个、第二个和第三个，最后将最后一个和第一个相连。你构建的篱笆段需要组成一个**无自交的多边形**。也就是说，每个篱笆桩只连接两段篱笆，且在其他任何点上都至多有一段篱笆通过。 做到这一步很容易，但你还希望尽可能保留农场的宽阔。你可不希望大部分农场被篱笆圈在外面。因此，你希望构建的篱笆所围成的面积，**要大于你可以只用一部分桩时能围成的最大面积的一半**。

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

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

**样例说明** 第一个测试用例中，共有三种可以构成的多边形，其中两种面积足够大，分别是序列 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 完成。