P13127 [GCJ 2019 Finals] Juggle Struggle: Part 2

本题的前两段（不包括本段）与“Juggle Struggle: Part 1”完全相同。除此之外，这两道题可以独立解决，你无需阅读或解决其中一道才能理解或解决另一道。 作为 Graceful Chainsaw Jugglers 团队的经理，你决定让表演更加精彩。你不再让每个杂技演员单独抛接自己的电锯，而是让他们两两组队，每对互相抛接电锯。在新的表演中，$2 \times \mathbf{N}$ 名杂技演员将同时登台，分成 $\mathbf{N}$ 对，每个杂技演员恰好属于一对。 你认为，如果不同杂技演员对抛接的电锯有相互碰撞的风险，表演会更加惊险。设舞台为一个二维平面，将一对杂技演员的位置用一条直线段连接，称为该对的“抛接路径”。当两对杂技演员的抛接路径相交时，说明他们抛接的电锯存在碰撞风险。我们将杂技演员的空间位置和分组方式称为一种“安排”。如果每一对杂技演员的抛接路径都与其他每一对的抛接路径相交，则称该安排为“壮观的”。也就是说，要使安排壮观，$\mathbf{N}$ 条抛接路径中的每一条都必须与其他 $\mathbf{N}-1$ 条路径相交（这些交点不必都在同一位置）。 经过最后的调整后，你认为你已经得到了一个壮观的安排。由于准备仓促，你希望编写一个检查程序，判断该安排是否真的壮观。如果不是，则最多有 25 对杂技演员的抛接路径未能与所有其他对的路径相交。你希望你的检查程序能列出所有这些未达标的杂技演员对，供进一步检查。

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例的数量。接下来有 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示杂技演员对的数量。接下来的 $\mathbf{N}$ 行，每行包含四个整数 $\mathbf{X}_\mathbf{i}$、$\mathbf{Y}_\mathbf{i}$、$\mathbf{X'}_\mathbf{i}$、$\mathbf{Y'}_\mathbf{i}$。其中 $(\mathbf{X}_\mathbf{i}, \mathbf{Y}_\mathbf{i})$ 和 $(\mathbf{X'}_\mathbf{i}, \mathbf{Y'}_\mathbf{i})$ 分别表示第 $i$ 对杂技演员两人的坐标。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $y$ 为大写单词 MAGNIFICENT，如果输入表示的是一个壮观的安排；否则，$y$ 应为一个严格递增的整数列表。整数 $i$ 应出现在该列表中，当且仅当第 $i$ 对杂技演员的抛接路径未能与至少一条其他抛接路径相交。

**样例解释** - 样例 1 中只有两对杂技演员，他们的抛接路径没有相交。 - 样例 2 中，所有对的抛接路径都两两相交，安排是壮观的。 - 样例 3 中，只有第 3 对的抛接路径与所有其他对的路径都相交。 **数据范围** - $-10^9 \leq \mathbf{X}_\mathbf{i} \leq 10^9$，对所有 $i$。 - $-10^9 \leq \mathbf{Y}_\mathbf{i} \leq 10^9$，对所有 $i$。 - $-10^9 \leq \mathbf{X'}_\mathbf{i} \leq 10^9$，对所有 $i$。 - $-10^9 \leq \mathbf{Y'}_\mathbf{i} \leq 10^9$，对所有 $i$。 - 不存在三点共线的情况。（这也意味着没有两名杂技演员处于同一位置。） - 除至多 25 对杂技演员外，其余所有对的抛接路径都与其他 $\mathbf{N} - 1$ 条路径相交。 - 注意：不一定存在一种分组方式能使安排壮观。 **测试点 1（5 分，公开）** - 时间限制：20 秒。 - $1 \leq \mathbf{T} \leq 100$。 - $2 \leq \mathbf{N} \leq 100$。 **测试点 2（30 分，隐藏）** - 时间限制：45 秒。 - $1 \leq \mathbf{T} \leq 13$。 - $2 \leq \mathbf{N} \leq 10^5$。 由 ChatGPT 4.1 翻译