CF1599H Hidden Fortress

这是一个交互题！ 作为你在伟大的泡泡战争中的贡献之一，你被分配到了寻找新建敌方堡垒的位置。你所生活的世界是一个巨大的 $10^9 \times 10^9$ 网格，网格中的每个方格的两个坐标都在 $1$ 到 $10^9$ 之间。 你已知敌方基地的形状是一个矩形，并且其边与网格的边平行。你们世界的人们非常害怕处于世界的边缘，因此你知道基地不会包含网格边缘上的任何方格（即 $x$ 或 $y$ 坐标为 $1$ 或 $10^9$ 的方格）。 为了帮助你定位基地，你获得了一个设备，你可以将其放置在网格上的任意方格，它会告诉你距离敌方基地最近的方格的曼哈顿距离。方格 $(a, b)$ 到方格 $(p, q)$ 的曼哈顿距离定义为 $|a-p| + |b-q|$。如果你试图将设备放在敌方基地内部，你会被敌人俘获。因此，你必须确保设备永远不会放在敌方基地内部。 不幸的是，这个设备由电池供电，且无法充电。这意味着你最多只能使用设备 $40$ 次。

输入包含你每次查询的返回结果。

你的代码可以通过输出 "? $i$ $j$"（$1 \leq i, j \leq 10^9$）将设备放置在网格上的任意方格。作为回应，你会收到该方格到敌方基地最近方格的曼哈顿距离，或者如果你将设备放在敌方基地内部或网格外部，则会收到 $-1$。 如果你收到 $-1$ 而不是正数，请立即退出，你将会看到错误答案的判定。否则，你可以获得任意判定，因为你的程序会继续从已关闭的流中读取。 你的查询次数不得超过 $40$ 次。 一旦你确定了敌方基地的位置，应输出 "! $x$ $y$ $p$ $q$"（$1 \leq x \leq p \leq 10^9, 1 \leq y \leq q \leq 10^9$），其中 $(x, y)$ 是敌方基地内部 $x$ 和 $y$ 坐标最小的方格，$(p, q)$ 是敌方基地内部 $x$ 和 $y$ 坐标最大的方格。注意，输出答案不计入 $40$ 次查询次数。 每次输出查询或答案后，别忘了输出换行并刷新输出流。否则，你会因为空闲超时而被判定为超时。具体方法如下： - C++：使用 fflush(stdout) 或 cout.flush()； - Java：使用 System.out.flush()； - Pascal：使用 flush(output)； - Python：使用 stdout.flush()； - 其他语言请参考相关文档。

由 ChatGPT 4.1 翻译