P13064 [GCJ 2020 #2] Wormhole in One

你正在参加一场星际超空间高尔夫比赛，并成功晋级决赛！为了确保胜利，你决定制定一个完美的策略。 在超空间高尔夫中，和传统高尔夫一样，你需要用球杆击球，使球朝你选择的方向飞行。比赛场地是一个二维平面，平面上的点代表不同的球洞。球本身也用一个点表示，你可以自由选择球的起始位置，只要不和任何球洞重合即可。 由于这是超空间高尔夫，选手可以将某些球洞对连接起来形成虫洞。每个球洞可以选择保持普通状态，或者最多与另一个球洞相连（不能自连）。虫洞是无向连接，可以双向穿越。 由于环境无摩擦，当你击球后，球会沿直线永远飞行，除非碰到球洞 $h$。当球碰到球洞 $h$ 时： - 如果 $h$ 没有连接其他球洞，球会停止； - 如果 $h$ 连接了另一个球洞 $h'$，球会立即从 $h'$ 飞出，并保持原来的飞行方向继续移动。 你已知所有球洞的位置。你的目标是通过一次击球，最大化触碰到的不同球洞数量。为此，你需要选择： 1. 球的起始位置 2. 球的飞行方向 3. 要连接成虫洞的球洞对（可选） 注意： - 球不能从虫洞位置开始 - 当球穿过虫洞时，进入和穿出的两个球洞都计入总数 - 每个球洞只计一次，即使多次进入或穿出 - 如果球停在某个球洞，该球洞也会被计入

输入第一行是测试用例数量 $T$。每个测试用例包含： - 第一行：整数 $N$ 表示球洞数量 - 接下来 $N$ 行：每行两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个球洞的坐标

对于每个测试用例，输出一行 `Case #x: y`，其中： - $x$ 是测试用例编号（从 1 开始） - $y$ 是在最优策略下能触碰到的最大不同球洞数量

**样例解释** 样例 #1：连接两个球洞形成虫洞，可以让球穿过两个球洞。如果不连接虫洞，球碰到第一个球洞就会停止，无法触碰多个球洞。  样例 #2：连接 $(0, 0)$ 和 $(5, 5)$ 的球洞。从 $(4.9, 5)$ 水平向右击球，依次经过 $(5, 5)$ → $(0, 0)$ → $(5, 0)$ 后停止。  样例 #3：连接 $(0, 0)-(5, 0)$ 和 $(3, 2)-(5, 5)$ 两对球洞。从 $(4, -1)$ 向 $(5, 0)$ 击球，依次经过 $(5, 0)$ → $(0, 0)$ → $(5, 5)$ → $(3, 2)$。  样例 #4：连接 $(0, 0)-(1, 1)$、$(2, 1)-(11, 2)$ 和 $(8, 2)-(14, 2)$ 三对球洞。从 $(-1, 0)$ 向 $(0, 0)$ 击球，可以经过所有 7 个球洞（某些球洞会被多次经过但只计一次）。  样例 #5：只有一个球洞时，直接击球入洞即可。  **数据范围** - $1 \leq T \leq 100$ - 球洞坐标范围：$-10^9 \leq X_i, Y_i \leq 10^9$ - 所有球洞坐标互不相同 **测试集 1（10 分，可见评测结果）** - $1 \leq N \leq 7$ **测试集 2（16 分，隐藏评测结果）** - $1 \leq N \leq 100$ 翻译由 DeepSeek V3 完成