← 返回题目列表

Codeforces · 1826/F

F. 淡入雾中

中文机器翻译题面 查看原题

这是一个交互问题。

在二维欧几里德平面上有 $$$n$$$ 个具有真实坐标的不同隐​​藏点。在一个查询中,您可以询问某一行 $$$ax + by + c = 0$$$ 并按某种顺序获取所有 $$$n$$$ 指向该行的投影。给定的预测并不准确,请阅读交互部分以获得更清晰的信息。

使用最少的查询次数,猜测所有 $$$n$$$ 点并按某种顺序输出它们。这里的极简性意味着用 $$$n$$$ 点解决任何可能的测试用例所需的最少查询数量。

隐藏点是预先固定的,并且在整个交互过程中不会改变。换句话说,交互器不具有适应性。

点 $$$A$$$ 到线 $$$ax + by + c = 0$$$ 的投影是线上最接近 $$$A$$$ 的点。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 50$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 25$$$) — 隐藏点的数量。

对于每个测试用例,保证对于任何一对隐藏点,它们的 $$$x$$$ 坐标至少相差 $$$1$$$。类似地,任何对的 $$$y$$$ 坐标也至少相差 $$$1$$$。

所有隐藏点的坐标 $$$x$$$ 和 $$$y$$$ 的绝对值不超过 $$$100$$$。

互动

要查询行 $$$ax + by + c = 0$$$,您应该打印“? a b c”,其中所有 a、b 和 c 都是绝对值最大为 $$$100$$$ 的实数。对于精度较低的问题,数字 $$$a$$$ 和 $$$b$$$ 必须满足条件 $$$|a| + |b| \geq 0.1$$$,其中 $$$|a|$$$ 是 $$$a$$$ 的绝对值。

作为查询的答案,您将获得“x_1 y_1 ... x_n y_n”形式的 $$$n$$$ 点,其中点 $$$(x_i, y_i)$$$ 是线 $$$ax + by + c = 0$$$ 的投影。保证每个打印点与真实投影点的距离不超过$$$10^{-4}$$$。每个坐标最多打印 9 位小数。

请参阅交互示例以更清楚地了解。

如果您询问太多问题,您将得到错误的答案。

要输出答案,您应该打印“! x_1 y_1 ... x_n y_n”,其中 $$$(x_i, y_i)$$$ 是隐藏点的坐标。您可以按任何顺序输出隐藏点。如果每个打印点与相应隐藏点的距离不超过 $$$10^{-3}$$$,则答案将被视为正确。打印答案不算作查询。

打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档

黑客

要进行破解,请使用以下测试格式。

在第一行输出一个整数 $$$t$$$ ($$$1 \leq t \leq 50$$$) — 测试用例的数量。

测试用例的描述如下。

在每个测试用例的第一行输出一个整数 $$$n$$$ ($$$2 \leq n \leq 25$$$)。在接下来的 $$$n$$$ 行中,每行输出两个有理数。 $$$i$$$ 行中的数字应分别对应于 $$$x_i$$$ 和 $$$y_i$$$。打印点必须符合输入部分的所有约束。

示例

输入 #1

1
2

1 1 2.5 1

1.500000001 1.500000000 2 2

输出 #1

? 0 1 -1

? 0.2 -0.2 0

! 1 3 2.5 0.500000001

注意

示例中的隐藏点为 $$$(1, 3)$$$ 和 $$$(2.5, 0.5)$$$

一张图片,描述了第一个查询:

一张图片,描述了第二个查询: