CF1715F Crop Squares

这是一个交互题。 Stanley 农夫在一个大小为 $n \times m$ 米的矩形田地里种植玉米，田地的四个角分别位于点 $(0, 0)$、$(0, m)$、$(n, 0)$、$(n, m)$。今年收成很好，玉米覆盖了整个田地。 在收获前夜，外星人到来，在田地内的某个边与田地边界平行的 $1 \times 1$ 的正方形内投放了毒药。这个正方形内的玉米不能食用，但你无法通过外观分辨出被毒害的玉米。Stanley 只能从任意多边形区域采集玉米样本，并送到实验室分析，实验室会告知该样本中被毒害玉米的面积。由于收成很快会变质，这样的实验最多只能进行 $5$ 次。 更正式地说，你最多可以进行 $5$ 次询问，每次询问会返回你选定的多边形与被毒害正方形的交面积。你需要找出被毒害正方形的左下角坐标（即 $x$ 和 $y$ 坐标最小的顶点）。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 100$），表示田地的大小。

每次询问多边形与被毒害正方形的交面积时，输出 $k+1$ 行，其中 $k$（$3 \le k \le 1000$）为多边形的顶点数。第一行为 "? k"。接下来的第 $i$ 行输出两个实数 $x_i$ 和 $y_i$（$|x_i|, |y_i| \le 10^4$），表示多边形第 $i$ 个顶点的坐标，最多保留 $15$ 位小数。 多边形必须有严格正面积且不能自交。 对于每次询问，你将收到一个实数 $s$（$0 \le s \le 1$，保留 $15$ 位小数），表示该多边形与被毒害正方形的交面积。如果多边形不合法，返回值不保证有效。 当你确定了被毒害正方形的位置后，输出一行 "! x y"，其中 $x$ 和 $y$ 为实数（最多 $15$ 位小数），表示被毒害正方形左下角的坐标（$0 \le x \le n-1$，$0 \le y \le m-1$），然后你的程序应当终止。 如果你的答案在两个坐标上的绝对误差或相对误差不超过 $10^{-6}$，则被认为是正确的。形式化地，设你的答案为 $a$，标准答案为 $b$，则当 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ 时，答案正确。 每次输出询问后不要忘记换行并刷新输出缓冲区，否则会因“Idleness limit exceeded”而判错。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 格式 制作 Hack 时，输入格式如下： 第一行输入两个整数 $n$ 和 $m$（$1 \le n,m \le 100$），表示田地的大小。 第二行输入两个实数 $x$（$0 \le x \le n-1$）和 $y$（$0 \le y \le m-1$），表示被毒害正方形左下角的坐标。

在题目描述中的第一个测试点，外星人在坐标为 $(1.5, 0.5)$、$(1.5, 1.5)$、$(2.5, 1.5)$、$(2.5, 0.5)$ 的四个点围成的正方形内投放了毒药。图中红色为被毒害的正方形，蓝色为一次询问选定的多边形，绿色为它们的交集。 第一次询问的示意图：  第二次询问的示意图：  由 ChatGPT 4.1 翻译