← 返回题目列表

Codeforces · 713/B

B. 搜索矩形

中文机器翻译题面 查看原题

Fiya 刚刚学习了新的几何对象——矩形。给他一个由 n × n 晶胞组成的场。行从下到上用 1 到 n 的整数进行编号。列从左到右用 1 到 n 的整数进行编号。位于r行和c列交叉处的单元格表示为(r,c)。 Filya 绘制了两个矩形,使得它们的边平行于坐标轴,并且每个单元完全位于它们的内部或完全外部。此外,两个矩形中都没有单元格。

后来,刺猬 Filya 对他的矩形的位置产生了兴趣,但找不到绘制它们的那张纸。它们被索尼娅拿走了,现在她想和菲利亚玩一个小游戏。他告诉她一个查询矩形,她回复完全位于给定查询矩形内的初始矩形的数量。查询矩形应与初始矩形匹配相同的条件。如果矩形的每个单元格都位于查询内,则矩形完全位于查询内。

Filya 非常了解 Sonya,因此可以肯定,如果他问超过 200 个问题,她就会停止回复。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 216) — 字段的大小。

对于每个查询,都会返回一个 0 到 2 之间的整数 - 完全位于查询矩形内的初始矩形的数量。

互动

要刷新,您可以使用(在打印整数和行尾之后):

- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。

如果您询问超过 200 个查询,或者打印了不正确的坐标,您将得到错误答案判决。

如果您不打印任何内容(但您应该)或者忘记刷新输出(更多信息如下),您将得到空闲限制超出的判决。

黑客攻击。

第一行应包含整数 n (2 ≤ n ≤ 216)。

第二行应包含四个整数 x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n) - 第一个矩形的描述。

第三行以类似的方式包含第二个矩形的描述。

输出

要进行查询,您必须打印“?x1 y1 x2 y2”(不带引号)(1 ≤ x1 ≤ x2 ≤ n,1 ≤ y1 ≤ y2 ≤ n),其中(x1,y1)代表查询左下单元格的位置,(x2,y2)代表查询右上角单元格的位置。您提出的问题不得超过 200 个。每次查询后,您应该执行“刷新”操作并读取答案。

如果您认为已经确定了两个矩形的位置(或用完查询),则应该打印“!x11 y11 x12 y12 x21 y21 x22 y22”(不带引号),其中前四个整数描述第一个矩形的左下角和右上侧的单元格,后面的四个整数描述第二个矩形的相应单元格。您可以按任意顺序打印矩形。打印答案后,打印行尾并执行“flush”。您的程序应该在打印答案后立即终止。

示例

输入 #1

5
2
1
0
1
1
1
0
1

输出 #1

? 1 1 5 5
? 1 1 3 3
? 1 1 3 1
? 2 2 2 2
? 3 3 5 5
? 3 3 3 5
? 3 3 3 4
? 3 4 3 5
! 2 2 2 2 3 4 3 5