問題文
这个问题是一个反应性问题。 有在飞机上 有 N 圆圈。这些圆的中心都是整数坐标,x、y坐标是 -1 \ 000 以上 1 \ 000 如下。另外,所有圆的半径都是 200 以上 1 \ 000 的整数。
Paken是Paken的一名新生,他正在尝试找出所有圆圈的信息,但他正在尝试计算圆圈的数量。 N 但不是。他可以向 E869120 询问以下问题: 我们可以问这样的问题:“
- 座標 (p, q) 落在里面有多少个圆圈?”我们假设边界也包括在内。 必须满足 -5 \ 000 \leq p, q \leq 5 \ 000 。 p, q 不必是整数。
PAKEN 为你编写一个程序,可以通过询问尽可能少的问题找出圆圈中的所有信息。
入出力
这个问题是一个交互问题。因此,输入输出格式与正常问题不同。1. 首先,您必须收到以下输入。
N
N 表示平面上存在的圆的数量。
2. 接下来,您必须提出问题。首先,要提出问题,您必须输出以下内容。
? p q
你 '?', p, q 该值应乘以以空格分隔一行 必须输出。这是坐标 (p, q) 的意思是问里面有多少个圆圈? p, q 可能是十进制数,但绝对值为 5 \ 000 必须小于或等于:
3. 问题的答案必须作为法官的输入收到,如下所示:
R
R 是一个整数,表示查询的坐标包含在多少个圆内。回答问题后,您必须转到步骤 2 或 4。
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 表示第 个圆的半径。
接听时, 输出必须跨越 N+1 行。 应输出
1 行表示, 有第 '!' 。 从行
2 开始, N 跨行圈出信息 (x_i, y_i, r_i) 必须按该顺序输出,并用空格分隔。 但是,输出顺序是基于中心坐标的。 x 按坐标升序排列, x 如果坐标相同 y 必须按坐标升序输出。
制約
- N 是 您也可以写 1 以上 20 的整数。
- 圆坐标 (x_i, y_i) 和圆的半径 r_i 满足问题陈述中写入的约束。
- 所有情况都是在约束范围内以均匀概率随机生成的。具体来说,对于每个圆,首先,圆心坐标为 (-1000, -1000) 减去 (1000, 1000) 最多 4004001 以均匀概率分布随机选取,则半径为 200 减去 1000 最多 801 是从具有均匀概率分布的备选方案中选择的。
注意
- 如果输出格式不正确,判断结果将不确定。 (
WA) - 输出结束时还需要flush,否则可能会出现TLE。
- 你, 不要问超过 50 \ 000 的问题。
小課題 / 得点
小課題1 [ 200点 ]
- N = 1 是。
- 子任务1的情况是 有 10 。 10 对于所有情况, 如果您可以在 50 \ 000 问题中找到答案,则您的答案正确。
小課題2 [ 1 \ 100点 ]
- N = 20 是。
- 子任务2的情况是 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 + floor(\frac{480000}{L*}) 可以得到第 1 向下舍入 分数四舍五入到 10 位。
- L* \leq 600 时, 1 \ 100 点満点.
输入/输出示例
例如, N = 2 和一个圆的中心坐标是 半径为 (4, 7) 半径是 2,另一个圆的中心坐标是 (3, 8) 半径是 3 情况下的输入/输出(交互式)示例如下所示。 输入
| 入力 | 出力 | 備考 |
|---|---|---|
| 2 | N 的值。 问有多少个圆圈包含 | |
| ? 0 0 | 座標 (0, 0) 。 | |
| 0 | 不包含在这两个圈子中。自然地 0 。 | |
| ? 4 6.5 | 座標 (4, 6.5) 。 | |
| 2 | 由于它包含在两个圈子中, 由于它只包含在 2 。 | |
| ? 1.5 10 | 座標 (1.5, 10) 。 | |
| 1 | (3, 8) 为中心的半径 有一个圆形房间,里面有 3 的圆圈中, 1 。 | |
|
! 3 8 3 4 7 2 |
(3, 8) 为中心的半径
有一个圆形房间,里面有 3 圈和,
回答有一个 (4, 7) 为中心的半径
有一个圆形房间,里面有 2 的圆圈。 注意,需要按照中心的x坐标升序输出,如果相同则按照中心的y坐标降序输出。 |
作者: E869120