AT_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 自动生成