P13126 [GCJ 2019 Finals] Juggle Struggle: Part 1

本题的前两段（不包括本段）与“Juggle Struggle: Part 2”完全相同。除此之外，这两道题可以独立解决；你无需阅读或解决其中一道题即可理解或解决另一道题。 作为 Graceful Chainsaw Jugglers 团队的经理，你决定让表演更加精彩。你不再让每位杂技演员单独抛接自己的电锯，而是让他们两两组队，每对互相抛接电锯。在这种新表演中，将有 $2 \times \mathbf{N}$ 名杂技演员同时登台，被分为 $\mathbf{N}$ 对，每位杂技演员恰好属于一对。 你认为，如果不同对的杂技演员所抛接的电锯有相互碰撞的风险，表演会更加惊险。设舞台为一个二维平面，连接一对杂技演员位置的直线段称为该对的抛接路径。当两条抛接路径相交时，称这两对杂技演员的电锯存在碰撞风险。我们称杂技演员的空间位置及其配对方式为一种“安排”。如果每两对杂技演员的电锯都存在碰撞风险，则称该安排为“壮观的安排”。 经过长时间的思考和设计，你想出了一个壮观的安排，并把杂技演员在舞台上的位置和配对方式记录在纸上。不幸的是，一次失误的电锯抛掷把纸张切成了两半，你丢失了记载配对方式的那一半。由于舞台布景已经根据杂技演员的位置设计好，这些位置无法更改。距离备受期待的首演只剩下几个小时，你需要重新找到一个壮观的安排！给定每位杂技演员在二维舞台上的位置，请找出一种配对方式，使得该安排是壮观的。

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例的数量。接下来有 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示杂技演员对数。接下来的 $2 \times \mathbf{N}$ 行，每行包含两个整数 $\mathbf{X}_\mathbf{i}$ 和 $\mathbf{Y}_\mathbf{i}$，表示第 $i$ 位杂技演员的位置坐标。

对于每个测试用例，输出一行，格式为 Case #x: $j_1$ $j_2$ $\dots$ $j_{2 \times \mathbf{N}}$，表示第 $i$ 位杂技演员应与第 $j_i$ 位杂技演员配对，对于每个 $i$ 都满足 $j_{j_i} = i$。

**样例解释** 在样例第 1 个测试用例中，杂技演员的位置构成一个正方形。唯一的有效方案是将第 1 位与第 3 位配对，第 2 位与第 4 位配对。 **数据范围** - $-10^9 \leq \mathbf{X}_\mathbf{i} \leq 10^9$，对所有 $i$ 成立。 - $-10^9 \leq \mathbf{Y}_\mathbf{i} \leq 10^9$，对所有 $i$ 成立。 - 任意三位杂技演员的位置不共线。（这也意味着没有两位杂技演员处于同一位置。） - 至少存在一种配对方式，使得最终安排是壮观的。 **测试点 1（5 分，公开）** - 时间限制：20 秒。 - $1 \leq \mathbf{T} \leq 100$。 - $2 \leq \mathbf{N} \leq 100$。 **测试点 2（30 分，隐藏）** - 时间限制：60 秒。 - $1 \leq \mathbf{T} \leq 10$。 - $2 \leq \mathbf{N} \leq 10^5$。 由 ChatGPT 4.1 翻译