如果平面上的一个点的坐标是小于或等于 $$$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$$$ for $$$i=1,2,\dots,k$$$)其中 $$$(x_1, y_1),\,(x_2, y_2),\,(x_3, y_3),\, \dots,\,(x_k, y_k)$$$ 是 $$$k$$$ 不同的允许选择点(点的顺序并不重要)。
当您确定了不可见矩形的周长 $$$p$$$ 后,您必须打印“! $$$p$$$”(不带引号)并终止程序。
如果您询问超过 $$$4$$$ 查询,或者其中一个查询格式错误,则交互器会立即终止,并且您的程序会收到“错误答案”的判决。
交互器可以是自适应的(即,在交互开始之前可能不会选择隐藏矩形)。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解解决方案,请使用以下格式。
输入只有一行,包含 $$$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)$$$ 是隐藏矩形的右上顶点。
请注意,对于黑客来说,交互不会是自适应的。
示例
输入 #1
13 5 123 80
输出 #1
输入 #2
2 2 4 4
输出 #2
输入 #3
1 1 200 200
输出 #3
注意
以下是第一个示例的交互示例,旨在显示查询的格式。 $$$$$$ \begin{array}{l|l|l} \text{查询(参赛程序)} & \text{回答(互动者)} & \text{解释} \\ \hline \mathtt{?\ 4} & & \text{我们选择 $4$ 个顶点} \\ \mathtt{13\ 5\ 13\ 80\ 123\ 5\ 123\ 80} & \mathtt{4} &\text{隐藏的矩形。}\\ \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章
对于第二个示例,可能的交互如下。 $$$$$$ \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)$$$ 的矩形,以蓝色显示。