CF1552H Guess the Perimeter

我们称平面上的一个点为“可选点”，如果它的坐标是正整数且不超过 $200$。 存在一个不可见的矩形，满足以下条件： - 它的顶点都是可选点； - 它的边平行于坐标轴； - 它的面积大于零。 你的任务是猜出这个矩形的周长。为此，你最多可以询问 $4$ 次。 每次询问，你可以选择一个非空的可选点集合，系统会告诉你你选中的点中有多少个在不可见矩形的内部或边界上。

无

要发起一次询问，请输出两行： - 第一行输出 "? $k$"，其中 $k$（$k \ge 1$）为你选择的点的数量。 - 第二行输出 $2k$ 个整数 $x_1,\, y_1,\, x_2,\, y_2,\, \dots,\, x_k,\, y_k$（$1 \le x_i, y_i \le 200$，$i=1,2,\dots,k$），表示你选择的 $k$ 个不同的可选点（点的顺序无关紧要）。 之后，你需要读取一个整数——表示你选择的点中有多少个在不可见矩形的内部或边界上。 当你确定了不可见矩形的周长 $p$ 后，输出 "! $p$" 并结束程序。 如果你询问超过 $4$ 次，或者某次询问格式不正确，交互器会立即终止，你的程序会收到 Wrong Answer 判定。 交互器可能是自适应的（即隐藏的矩形可能不是在交互开始前就选定的）。 每次输出询问后不要忘记输出换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hacks 要对本题进行 Hack，请使用如下格式。 输入仅一行，包含 $4$ 个整数 $x_0$、$y_0$、$x_1$、$y_1$（$1 \le x_0 < x_1 \le 200$，$1 \le y_0 < y_1 \le 200$），其中 $(x_0, y_0)$ 是隐藏矩形的左下角顶点，$(x_1, y_1)$ 是右上角顶点。 注意，对于 Hack，交互器不会是自适应的。

以下是第一个样例的交互示例，展示了询问的格式。 $$ \begin{array}{l|l|l} \text{询问（选手程序）} & \text{回答（交互器）} & \text{说明} \\ \hline \mathtt{?\ 4} & & \text{我们选择了矩形的 $4$ 个顶点} \\ \mathtt{13\ 5\ 13\ 80\ 123\ 5\ 123\ 80} & \mathtt{4} & \\ \hline \mathtt{?\ 5} & & \text{我们选择了矩形外的 $4$ 个点} \\ \mathtt{100\ 4\ 100\ 81\ 12\ 40\ 124\ 40\ 50\ 50} & \mathtt{1} & \text{以及点 $(50,50)$。} \\ \hline \mathtt{?\ 2} & & \text{我们选择了点 $(1, 1)$} \\ \mathtt{200\ 200\ 1\ 1} & \mathtt{0} & \text{和 $(200,200)$。} \\ \hline \mathtt{!\ 370} & & \text{这是正确的周长。} \end{array} $$ 对于第二个样例，一种可能的交互如下： $$ \begin{array}{l|l|l} \text{询问（选手程序）} & \text{回答（交互器）} & \text{说明} \\ \hline \mathtt{?\ 4} & & \text{我们选择了点 $(3, 2)$、$(4, 1)$、} \\ \mathtt{3\ 2\ 4\ 1\ 5\ 2\ 4\ 3} & 2 & \text{$(5, 2)$ 和 $(4, 3)$。} \\ \hline \mathtt{?\ 7} & & \text{我们选择了点 $(1, 4)$、$(2, 4)$、} \\ \mathtt{1\ 4\ 2\ 4\ 1\ 5\ 2\ 5\ 5\ 5\ 5\ 6\ 6\ 5} & 1 & \text{$(1, 5)$、$(2, 5)$、$(5, 5)$、$(5, 6)$ 和 $(6, 5)$。} \\ \hline \mathtt{!\ 8} & & \text{这是正确的周长。} \end{array} $$ 情况如下图所示： 绿色点为第一次询问的点，橙色点为第二次询问的点。可以看到，只有两个矩形与交互器的回答一致： - 顶点为 $(2, 2)$ 和 $(4, 4)$ 的矩形（红色）； - 顶点为 $(4, 2)$ 和 $(5, 5)$ 的矩形（蓝色）。 由于这两个矩形的周长都是 $8$，因此最终答案为 $8$。 由 ChatGPT 4.1 翻译