[THUPC2021 初赛] 非欧几何

ustze 喜欢几何，他认为几何是数学竞赛中最简单的一环，在征服了数学以后，ustze 决定将自己的天赋带到计算几何中，并与传统的欧氏几何展开较量。 作为欧氏几何的捍卫者，Tinytree 在三维空间中建立了一个**球心在原点、半径为** $\boldsymbol R$ **的球面**，其中坐标为 $(0,0,R)$ 的点称为北极点，显然北极点处于球面上。Tinytree 回忆在欧氏几何中，三点可以唯一确定空间中的一个圆，因此 Tinytree 在球面上确定了 $N$ 个点对，其中每个点对和北极点一起就确定了一个球面上的圆，我们保证这些圆的**半径严格小于** $\boldsymbol R$，因此每个圆会将球面分成面积不相等的两部分，我们**称球面上面积较小的部分是该圆的内部，面积较大的部分是该圆的外部**，而这 $N$ 个圆的内部受到 Tinytree 的保护，**它们的并构成安全区域**。 作为非欧几何的狂热者，ustze 认为球面上的圆其实是“直线”，他在球面上确定了 $M$ 个点对，其中每个点对和北极点一起也确定了一个球面上的圆，这些圆的**半径也是严格小于** $\boldsymbol R$ 的，这 $M$ 个圆的内部受到 ustze 的威慑，**它们的并构成危险区域**。 正当 Tinytree 和 ustze 对峙时，球面上一般路过一个 Kiana，她见到这幅景象十分害怕，开始在球面上东躲西藏。现在 Kiana 初步确定了 $T$ 个球面上的点，她想知道这些点是否在安全区域或危险区域中，以便自己跑路，由于 Kiana 自己不会算，所以希望你能够帮助她。

第一行包含三个正整数 $N, M$ 和 $T$（$1 \le N, M \le 5000$，$1 \le T \le 1.5 \times {10}^5$），分别表示 Tinytree 确定的点对数、ustze 确定的点对数和 Kiana 确定的跑路点数。 第二行包含一个正整数 $R$（$1 \le R \le {10}^3$），表示球面的半径大小。 接下来 $N$ 行，第 $i$ 行依次输入 $A_i, B_i, X_i, C_i, D_i, Y_i$（$1 \le |A_i|, |B_i|, |C_i|, |D_i| \le R$，$1 \le A_i^2 + B_i^2, C_i^2 + D_i^2 \le R^2$），其中 $A_i, B_i$ 表示 Tinytree 确定的第 $i$ 个点对中第一个点的横坐标和纵坐标，而 $X_i$ 为 `+` 表示第一个点的竖坐标大于 $0$，为 `-` 表示第一个点的竖坐标小于 $0$，如果竖坐标等于 $0$ 则 $X_i$ 是在 `+` 和 `-` 中随机选择的，$C_i, D_i$ 表示 Tinytree 确定的第 $i$ 个点对中第二个点的横坐标和纵坐标，$Y_i$ 表示竖坐标的正负，含义与 $X_i$ 相同。 接下来 $M$ 行，第 $j$ 行依次输入 $A_j, B_j, X_j, C_j, D_j, Y_j$（$1 \le |A_j|, |B_j|, |C_j|, |D_j| \le R$，$1 \le A_j^2 + B_j^2, C_j^2 + D_j^2 \le R^2$），表示 ustze 确定的第 $j$ 个点对坐标，点的表示方式与之前相同。 接下来 $T$ 行，第 $k$ 行包含两个实数 $A_k, B_k$（$1 \le |A_k|, |B_k| \le R$，$1 \le A_k^2 + B_k^2 \le R^2$）和一个字符 $X_k$，表示 Kiana 确定的第 $k$ 个跑路点，点的表示方式与之前相同。 数据保证合法，且输入中没有两个点是相同的，所有实数保留到小数点后三位，**Kiana 的跑路点和任意一个给定圆周的最小直线距离不小于** $\boldsymbol{{10}^{-6}}$。

输出共 $T$ 行，每行包含一个字符串，若 Kiana 的第 $k$ 个跑路点在安全区域中则在第 $k$ 行输出 `Safe`，如果不在安全区域中但也不在危险区域中则在第 $k$ 行输出 `Passer`，如果不在安全区域中且在危险区域中则在第 $k$ 行输出 `Goodbye`（所有输出不含引号）。

2 2 4
3
2.571 0.514 + 2.571 -0.514 +
-2.571 0.514 + -2.571 -0.514 +
0.514 2.571 + -0.514 2.571 +
0.514 -2.571 + -0.514 -2.571 +
2.118 -2.118 -
1.051 1.051 +
-0.468 1.870 +
-1.870 -0.468 +

Passer
Safe
Goodbye
Safe

在三维空间中，我们可以用一个有序的实数三元组 $(x, y, z)$ 来描述一个点的位置，其中 $x, y, z$ 分别称作这个点的横坐标、纵坐标和竖坐标。 三维空间中一个球心在 $(x_0, y_0, z_0)$、半径为 $R$ 的球面是指空间中所有满足 $(x - x_0)^2 + (y - y_0)^2 + (z - z_0)^2 = R^2$ 的点 $(x, y, z)$ 构成的点集，对于该球面上给定的两个不同点 $(x_1, y_1, z_1), (x_2, y_2, z_2)$，如果它们不是一对对踵点（两个点是对踵点当且仅当它们之间的距离为 $2 R$），则它们和球心不在同一直线上，这三个点唯一确定了一个平面，这个平面与球面的交线被这两个点分成了两个部分，其中较短部分的长度称为这两点在该球面上的距离，如果这两个点是对踵点，则定义它们之间的距离为 $\pi R$，球面上的一个圆指到球面上某点的球面距离等于一个常数的球面上的点的集合，可以证明球面上的任意三个不同点唯一确定了一个球面上的圆。 **【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。 题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。