P13182 [GCJ 2017 Finals] Omnicircumnavigation

勇敢的环球旅行者 K（她也许就是本题的作者）最近频繁地旅行。在最近的一次旅途中，她从 San Francisco 出发，途经 Frankfurt、Johannesburg、Abu Dhabi、Singapore、Tokyo，最后又回到了 San Francisco。在这次旅行中，她沿着一条闭合路径环绕地球一周，并且这条路径经过了每一个子午线。换句话说，对于每一个可能的经度，这条路径上至少有一个点位于该经度。 然而，K 并不确定这趟旅程是否真的称得上非常酷，因为实际上也可以通过飞到北极再围着北极走一圈来环绕地球，这似乎也并不特别困难（当然飞到北极本身除外）。于是她决定提出一个更广义的“环绕地球”的定义。这个新概念被称为 **omn icircumnavigation** —— 即无论如何放置地球的两极，这条闭合路径都能称为一次环绕地球。换句话说，**omn icircumnavigation** 是指地球表面上的一条闭合路径，它会经过每一个可能的半球。（只要碰到半球的边界也算经过。）等价地说，**omn icircumnavigation** 会与每一个可能的大圆（即球面上直径最大的圆）相交。 现在给定球面上半径为 $1$ 的球上的一系列 $N$ 个点。你需要判断，依次连接这些点所形成的路径是否为一次 **omnicircumnavigation**。路径的构造方式是：依次将每对相邻点沿球面最短路径连接起来，并将最后一个点与第一个点也以同样方式连接。任意一对相邻点（包括最后一个点与第一个点）都不会与原点共线。（也就是说，它们不是对踵点——即球面上的正反两点——也不代表球面上的同一个点。）

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例的数量。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行为一个整数 $\mathbf{N}$，表示 K 访问的城市数量。接下来的 $\mathbf{N}$ 行，每行包含三个整数 $\mathbf{X}_{\mathbf{i}}, \mathbf{Y}_{\mathbf{i}}, \mathbf{Z}_{\mathbf{i}}$。列表中的第 $i$ 个点的坐标为 $\left(\mathbf{X}_{\mathbf{i}} / \operatorname{sqrt}\left(\mathbf{X}_{\mathbf{i}}^{2}+\mathbf{Y}_{\mathbf{i}}^{2}+\mathbf{Z}_{\mathbf{i}}^{2}\right),\ \mathbf{Y}_{\mathbf{i}} / \operatorname{sqrt}\left(\mathbf{X}_{\mathbf{i}}^{2}+\mathbf{Y}_{\mathbf{i}}^{2}+\mathbf{Z}_{\mathbf{i}}^{2}\right),\ \mathbf{Z}_{\mathbf{i}} / \operatorname{sqrt}\left(\mathbf{X}_{\mathbf{i}}^{2}+\mathbf{Y}_{\mathbf{i}}^{2}+\mathbf{Z}_{\mathbf{i}}^{2}\right)\right)$。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 为测试用例编号，$y$ 为 `YES` 或 `NO`，表示该路径是否为一次 **omnicircumnavigation**。

**样例解释** 在样例第 1 组中，这三个点分别位于球面上同一个卦限的表面，路径刚好围成了这个卦限。实际上，有许多半球完全不与这条路径相交。 在样例第 2 组中，这八个点是内切于球体的立方体的八个顶点；无论如何选取半球，至少都会与路径的某些部分相交。注意，如果将所有坐标除以 $5$，得到的情况是等价的（点的集合相同）。 在样例第 3 组中，这条路径本身就是一个大圆，因此任意其他大圆都必定会与其有交点。 样例第 4 组使用了与样例第 3 组相同的三个点，只是前两个点各出现了两次。注意，一个测试用例中可以多次出现同一个点，同一条路径也可以多次经过同一个点或连接。 **限制条件** - $1 \leqslant \mathbf{T} \leqslant 200$。 - 对所有 $i$，$-10^{6} \leqslant \mathbf{X}_{\mathbf{i}} \leqslant 10^{6}$。 - 对所有 $i$，$-10^{6} \leqslant \mathbf{Y}_{\mathbf{i}} \leqslant 10^{6}$。 - 对所有 $i$，$-10^{6} \leqslant \mathbf{Z}_{\mathbf{i}} \leqslant 10^{6}$。 - 对所有 $i$，$\left(\mathbf{X}_{\mathbf{i}}, \mathbf{Y}_{\mathbf{i}}, \mathbf{Z}_{\mathbf{i}}\right)$ 至少有一个值不为 $0$。对于所有 $i, j$ 满足 $(i+1 = j)$ 或 $(i = \mathbf{N}-1$ 且 $j = 0)$，$\left(\mathbf{X}_{\mathbf{i}}, \mathbf{Y}_{\mathbf{i}}, \mathbf{Z}_{\mathbf{i}}\right)$ 和 $\left(\mathbf{X}_{\mathbf{j}}, \mathbf{Y}_{\mathbf{j}}, \mathbf{Z}_{\mathbf{j}}\right)$ 互不为整数倍关系。（任意一对相邻点，包括最后一个点和第一个点，都不是对踵点或球面上的同一个点。） **小数据集（测试集 1 - 可见）** - 时间限制：~~60~~ 15 秒。 - $3 \leqslant \mathbf{N} \leqslant 50$。 **大数据集（测试集 2 - 隐藏）** - 时间限制：~~300~~ 75 秒。 - $3 \leqslant \mathbf{N} \leqslant 5000$。 翻译由 GPT4.1 完成。