P13057 [GCJ 2020 #1B] Blindfolded Bullseye
题目描述
Gary 有一面巨大的正方形墙，高度和宽度均为 $2 \times 10^{9}$ 纳米。Gary 在墙上放置了一个圆形飞镖靶。飞镖靶的半径 $R$ 介于 $\mathbf{A}$ 和 $\mathbf{B}$ 纳米之间（含端点），且完全位于墙内（允许接触边缘）。飞镖靶的中心与墙的每条边的距离均为整数纳米。
Gary 邀请了他的朋友 Mika 来玩一个有趣的游戏。Gary 蒙住 Mika 的眼睛，并挑战她向飞镖靶的中心投掷飞镖。为了帮助她，每当 Mika 向墙上投掷飞镖时，Gary 会告诉她飞镖是否击中了飞镖靶。
Mika 不知道飞镖靶在墙上的具体位置，但由于她投掷飞镖的技术非常高超，可以精确到纳米级别。也就是说，她可以瞄准并击中墙上任意一个与边缘距离为整数纳米的点。每次投掷后，Gary 会立即告诉她是否击中了飞镖靶的中心、飞镖靶的其他部分，或者完全未击中飞镖靶（即击中墙面）。
你能帮助 Mika 在不超过 300 次投掷的情况下击中飞镖靶的中心吗？
### 交互协议
初始时，你的程序应读取一行，包含三个整数 $\mathbf{T}$、$\mathbf{A}$ 和 $\mathbf{B}$，分别表示测试用例的数量以及飞镖靶半径的最小值和最大值（单位为纳米）。（注意，$\mathbf{A}$ 和 $\mathbf{B}$ 在同一测试集中对所有测试用例相同。）然后，你需要处理 $\mathbf{T}$ 个测试用例。
我们将可投掷的点表示为 $(x, y)$，其中 $x$ 和 $y$ 是介于 $-10^{9}$ 和 $10^{9}$ 之间的整数。点 $(x, y)$ 表示该点距离墙的左边缘 $x + 10^{9}$ 纳米，距离墙的底边缘 $y + 10^{9}$ 纳米。因此，点 $(0, 0)$ 位于墙的正中心。
对于每个测试用例，裁判会秘密选择一个飞镖靶的半径 $R$ 和中心 $(X, Y)$。$R$、$X$ 和 $Y$ 是裁判为每个测试用例设计的整数（非随机），且满足题目限制。对于每个测试用例，你最多可以与裁判进行 300 次交互。你的程序代表 Mika，裁判程序代表 Gary。每次交互包含以下步骤：
1. 你的程序输出一行，包含两个整数 $X_{i}$ 和 $Y_{i}$（均在 $-10^{9}$ 到 $10^{9}$ 之间），表示投掷的坐标。
2. 裁判会响应一行，内容为以下之一：
- `CENTER`：如果 $X_{i} = X$ 且 $Y_{i} = Y$（即击中中心）。
- `HIT`：如果 $0 < (X - X_{i})^{2} + (Y - Y_{i})^{2} \leq R^{2}$（即击中飞镖靶但未击中中心）。
- `MISS`：其他情况（未击中飞镖靶）。
当裁判返回 `CENTER` 后，它会开始等待下一个测试用例的交互（如果有）。
如果你的输出格式错误或超出范围，裁判会返回 `WRONG`。如果在 300 次交互内未收到 `CENTER`，或者收到 `WRONG`，裁判会终止通信并判定为错误答案。如果成功在第 $T$ 个测试用例返回 `CENTER`，裁判会终止通信并判定为正确。如果程序超时或内存超限，会相应判定。
输入格式
参见交互协议。
输出格式
参见交互协议。
说明/提示
**样例解释**
以下是一个使用测试集 1 限制的样例交互：
```
// 读取 t = 20, a = 999999995, b = 999999995
t, a, b = readline_int_list()
// 裁判秘密选择 R = 999999995 和 X = -1, Y = 3
// 尝试投掷到墙的左上角，未击中飞镖靶
printline -1000000000 1000000000 to stdout
flush stdout
r = readline_string() // 返回 MISS
// 尝试投掷到墙的中心，击中飞镖靶但未击中中心
printline 0 0 to stdout
flush stdout
r = readline_string() // 返回 HIT
// 幸运地直接投掷到飞镖靶中心
printline -1 3 to stdout
flush stdout
r = readline_string() // 返回 CENTER
// 裁判开始下一个测试用例，选择 R = 999999995, X = 5, Y = 5
// 尝试投掷超出允许范围
printline -1234567890 1234567890 to stdout
flush stdout
r = readline_string() // 返回 WRONG
exit // 退出以避免超时错误
```
你可以使用[交互测试工具](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)在本地或平台上测试。工具的使用说明包含在注释中。请注意，该工具并非真实裁判系统，行为可能有所不同。
**数据范围**
- $1 \leqslant \mathbf{T} \leqslant 20$。
- $\mathbf{A} \leqslant \mathbf{R} \leqslant \mathbf{B}$。
- $-10^{9} + \mathbf{R} \leqslant \mathbf{X} \leqslant 10^{9} - \mathbf{R}$。
- $-10^{9} + \mathbf{R} \leqslant \mathbf{Y} \leqslant 10^{9} - \mathbf{R}$。
**测试集 1（3 分，可见判定）**
- $\mathbf{A} = \mathbf{B} = 10^{9} - 5$。
**测试集 2（12 分，可见判定）**
- $\mathbf{A} = \mathbf{B} = 10^{9} - 50$。
**测试集 3（19 分，隐藏判定）**
- $\mathbf{A} = 10^{9} / 2$。
- $\mathbf{B} = 10^{9}$。
翻译由 DeepSeek V3 完成