AT_tkppc3_j 円の重なり

[问题网址]: https://atcoder.jp/contests/tkppc3/tasks/tkppc3_j 配点：1300点 **这是一道交互式问题。** 平面上有 $N$ 个圆，这些圆的中心坐标都是整数值，$x$ 和 $y$ 的范围在 $-1\ 000$ 到 $1\ 000$ 之间。而这些圆的半径在 $200$ 到 $1\ 000$ 的整数之间。 新生 PAKEN 君想弄清楚所有圆的信息，但目前他只知道圆的数量 $N$。他可以向 E869120 询问以下问题： - 问某个坐标 $(p, q)$ 被多少个圆覆盖。坐标是在圆的边界上也算作被覆盖。坐标 $p$ 和 $q$ 需满足 $-5\ 000 \leq p, q \leq 5\ 000$，可以是小数。 请帮 PAKEN 君设计一个程序，让他尽可能少地询问就能确定所有圆的信息。 ### 输入与输出格式 **注意：这是交互式问题，输入输出格式与常规问题不同。** 1. 首先，你将接收到如下输入： > $N$ 其中 $N$ 是平面上圆的个数。 2. 接下来，你需要进行询问。为此，你需要输出如下格式： > $?$ $p$ $q$ 用空格隔开的 `?`、$p$ 和 $q$ 表示询问坐标 $(p, q)$ 被多少个圆包含。$p, q$ 可以是小数，绝对值不得超过 $5,000$。 3. 对于每次询问，裁判程序会返回一个整数 $R$，表示坐标被多少个圆包含： > $R$ 每次获得答案后，你可以继续询问或直接作答。 4. 当你已经确定所有圆的信息时，你需要停止询问并输出答案。答案格式如下： > $!$ $x_1$ $y_1$ $r_1$ $x_2$ $y_2$ $r_2$ ... $x_N$ $y_N$ $r_N$ 其中 $(x_i, y_i)$ 是第 $i$ 个圆的中心，$r_i$ 是第 $i$ 个圆的半径。 输出答案时，需要第一行输出`!`，从第二行起输出每个圆的信息，具体需要按照圆心的 $x$ 坐标升序输出；若 $x$ 相同，则按 $y$ 升序排列。

无

无

- $N$ 的范围是 $1$ 到 $20$。 - 圆的坐标和半径在题目中已给定的限制范围之内。 - 每个测试用例中的圆都是在这些约束下随机生成的。具体来说，圆的中心坐标均匀随机选自 $(-1000, -1000)$ 到 $(1000, 1000)$ 的 $4004001$ 种组合，半径则在 $200$ 到 $1000$ 之间的 $801$ 种可能中随机选择。 ### 注意 - 如果输出格式不正确，结果可能无法预测（不一定会返回 `WA`）。 - **输出时必须刷新缓冲，否则可能会因超时而失败。** - **询问次数不允许超过 $50,000$ 次。** ### 子任务 / 得分 子任务 1 [200 分] - $N = 1$。 - 共计 $10$ 个测试用例，若在不超过 $50,000$ 次询问中完成，可以得满分。 子任务 2 [1100 分] - $N = 20$。 - 共计 $20$ 个测试用例，全部在 $50,000$ 次查询内完成即可得分，根据询问次数多少，得分可能会有所调整。 假设最难的一个用例询问了 $L*$ 次，得分如下： - $25,001 \leq L* \leq 50,000$ 时，得 200 分。 - $9,001 \leq L* \leq 25,000$ 时，得 280 分。 - $3,001 \leq L* \leq 9,000$ 时，得 350 分。 - $2,001 \leq L* \leq 3,000$ 时，得 450 分。 - $601 \leq L* \leq 2,000$ 的情况下，得 $300 + \left\lfloor \frac{480000}{L*} \right\rfloor$ 的十分位取整分数。 - $L* \leq 600$ 时，得满分 1100 分。 ### 输入输出示例 假设 $N = 2$，一个圆的中心为 $(4, 7)$，半径为 $2$；另一个圆的中心为 $(3, 8)$，半径为 $3$。下面是交互过程的一个示例： 输入输出说明： 首先输入 $N$ ＝ $2$，���示有两个圆。 接着进行询问： - `? 0 0`，裁判返回 `0`，说明点 $(0, 0)$ 不在任何圆内。 - `? 4 6.5`，裁判返回 `2`，说明点 $(4, 6.5)$ 在两个圆内。 - `? 1.5 10`，裁判返回 `1`，说明点 $(1.5, 10)$ 在一个圆内。 确定圆的信息后进行输出： ``` ! 3 8 3 4 7 2 ``` 表示有两个圆，分别是中心坐标 $(3, 8)$ 半径 $3$ 和中心坐标 $(4, 7)$ 半径 $2$。特别注意，最后输出按照中心坐标 $x$ 较小的先输出，如果 $x$ 相同则按 $y$ 升序。 **本翻译由 AI 自动生成**