这是一个交互问题。
在二维欧几里德平面上有 $$$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)$$$
一张图片,描述了第一个查询:
一张图片,描述了第二个查询: