← 返回题目列表

Codeforces · 1715/F

F. 裁剪方块

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

这是一个交互问题。

农民 Stanley 在一块大小为 $$$ n \times m $$$ 米的矩形田地上种植玉米,其角点为 $$$(0, 0)$$$、$$$(0, m)$$$、$$$(n, 0)$$$、$$$(n, m)$$$。今年粮食丰收,玉米长满了整片田地。

收获前一天晚上,外星人抵达并在一个 $$$1 \times 1$$$ 正方形(边与田地边界平行)中对玉米下了毒。广场里面的玉米一定不能吃,但你从视觉上无法区分它和普通玉米。斯坦利只能从任意多边形中收集玉米样本并将其带到实验室,在那里对其进行分析,然后斯坦利将被告知样本中有毒玉米的数量。由于收成很快就会恶化,因此此类研究最多可进行 $$$5$$$ 次。

更正式地说,允许进行不超过 $$$5$$$ 的查询,每个查询都会计算所选多边形与有毒玉米正方形的交集面积。需要找出所画正方形的左下角坐标($$$x$$$和$$$y$$$坐标最小的正方形的顶点)。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 100$$$) - 字段大小。

互动

查询多边形与 $$$k$$$ ($$$3 \le k \le 1000$$$) 顶点在坐标为 $$$(x_1, y_1) 的点处的交面积,\; \dots ,\;(x_k, y_k)$$$ 带有方形有毒玉米打印 $$$k+1$$$ 行。在第一行中打印“? k”。在接下来的 $$$k$$$ 行的第 $$$i$$$ 中,打印两个实数 $$$x_i$$$ 和 $$$y_i$$$ ($$$|x_i|, |y_i| \le 10^4$$$),小数点后最多有 $$$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}$$$,您的答案将被视为正确。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

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

黑客

要进行破解,请使用以下测试格式。

输入的第一行应包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 100$$$) — 字段大小。

第二行应包含两个实数 $$$x$$$ ($$$0 \le x \le n - 1$$$) 和 $$$y$$$ ($$$0 \le y \le m - 1$$$) — 有毒玉米方块左下角的坐标。

示例

输入 #1

3 3





0.5





0.5

输出 #1

? 4
0 0
2 0
2 3
0 3

? 4
0 0
0 1
3 1
3 0

! 1.5 0.5

注意

在该声明的第一个测试中,外星人对一个玉米方体下了毒,其顶点坐标为 $$$(1.5, 0.5)$$$、$$$(1.5, 1.5)$$$、$$$(2.5, 1.5)$$$、$$$(2.5, 0.5)$$$。图中,它是红色的,查询中选择的多边形是蓝色的,它们的交集是绿色的。

第一个查询的图片:

第二个查询的图片: