Crop Squares

题意翻译

**这是一道交互题** 有一个 $n \times m$ 的长方形，四个角的坐标分别为 $ (0, 0) $ , $ (0, m) $ , $ (n, 0) $ , $ (n, m) $。在长方形里面有一个 $1 \times 1$ 的正方形，边平行于长方形边界。你需要询问出这个正方形的位置。每次询问，每次你可以询问正方形与你提问的多边形的相交面积。你最多可以进行 $5$ 次询问。

题目描述

This is an interactive problem. Farmer Stanley grows corn on a rectangular field of size $ n \times m $ meters with corners in points $ (0, 0) $ , $ (0, m) $ , $ (n, 0) $ , $ (n, m) $ . This year the harvest was plentiful and corn covered the whole field. The night before harvest aliens arrived and poisoned the corn in a single $ 1 \times 1 $ square with sides parallel to field borders. The corn inside the square must not be eaten, but you cannot distinguish it from ordinary corn by sight. Stanley can only collect a sample of corn from an arbitrary polygon and bring it to the laboratory, where it will be analyzed and Stanley will be told the amount of corn in the sample that was poisoned. Since the harvest will soon deteriorate, such a study can be carried out no more than $ 5 $ times. More formally, it is allowed to make no more than $ 5 $ queries, each of them calculates the area of intersection of a chosen polygon with a square of poisoned corn. It is necessary to find out the coordinates of the lower-left corner of the drawn square (the vertex of the square with the smallest $ x $ and $ y $ coordinates).

输入输出格式

输入格式

First line contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 100 $ ) — field sizes.

输出格式

In order to query the area of intersection of a polygon with $ k $ ( $ 3 \le k \le 1000 $ ) vertices at points with coordinates $ (x_1, y_1),\; \dots ,\;(x_k, y_k) $ with a square of poisoned corn print $ k+1 $ lines. In the first of these lines print "? k". In the $ i $ -th of the next $ k $ lines print two real numbers $ x_i $ and $ y_i $ ( $ |x_i|, |y_i| \le 10^4 $ ) with at most $ 15 $ digits after decimal place. The polygon must have strictly positive area and contain no self-intersections. In response to this query you will receive a real number $ s $ ( $ 0 \le s \le 1 $ ) with $ 15 $ digits after decimal place — the area of intersection of the square with the given polygon. If the polygon is invalid, there is no guarantee on the valid response. When you have identified the drawn square, print on a separate line "! x y", where $ x $ and $ y $ are real numbers with at most $ 15 $ digits after decimal place representing the coordinates of its lower-left corner ( $ 0 \le x \le n - 1 $ , $ 0 \le y \le m - 1 $ ), and then you have to terminate your program. Your answer will be considered correct if its absolute or relative error on both coordinates does not exceed $ 10^{-6} $ . Formally let your answer be $ a $ , jury answer be $ b $ . Your answer will be considered correct if $ \frac{|a-b|}{max(1,|b|)} \le 10^{-6} $ . After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Hacks To make a hack, use the following test format. The first line of the input should contain two integers $ n $ and $ m $ ( $ 1 \le n,m \le 100 $ ) — field sizes. The second line should contain two real numbers $ x $ ( $ 0 \le x \le n - 1 $ ) and $ y $ ( $ 0 \le y \le m - 1 $ ) — coordinates of the lower-left corner of the square of poisoned corn.

输入输出样例

输入样例 #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

说明

In the first test from the statement, the aliens poisoned a square of corn with vertices at points with coordinates $ (1.5, 0.5) $ , $ (1.5, 1.5) $ , $ (2.5, 1.5) $ , $ (2.5, 0.5) $ . In the picture, it is red, the polygon selected in the query is blue, and their intersection is green. Picture for the first query: Picture for the second query: 

**题目大意：**
这是一道交互式问题。有一个 $ n \times m $ 的长方形区域，四个角的坐标分别为 $ (0, 0) $, $ (0, m) $, $ (n, 0) $, $ (n, m) $。在这个长方形内有一个 $ 1 \times 1 $ 的正方形，其边与长方形边界平行。你需要通过询问来确定这个正方形的位置。每次询问，你可以询问一个多边形与你提问的正方形的相交面积。你最多可以进行 5 次询问。

**输入输出数据格式：**
- **输入格式：** 第一行包含两个整数 $ n $ 和 $ m $ ($ 1 \le n, m \le 100 $) — 长方形区域的大小。
- **输出格式：** 为了查询一个有 $ k $ ($ 3 \le k \le 1000 $) 个顶点的多边形与毒害正方形的相交面积，需要打印 $ k+1 $ 行。在第一行打印 "? k"。在接下来的 $ k $ 行中，每行打印两个实数 $ 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} $，则你的答案被认为是正确的。

打印查询后，不要忘记输出换行符并刷新输出。否则，你将得到超时限制。对于不同的语言，使用相应的方法来刷新输出。

- **输入输出样例：**
- **输入样例 #1：**
```
3 3
```
- **输出样例 #1：**
```
? 4
0 0
2 0
2 3
0 3

? 4
0 0
0 1
3 1
3 0

! 1.5 0.5
```**题目大意：** 这是一道交互式问题。有一个 $ n \times m $ 的长方形区域，四个角的坐标分别为 $ (0, 0) $, $ (0, m) $, $ (n, 0) $, $ (n, m) $。在这个长方形内有一个 $ 1 \times 1 $ 的正方形，其边与长方形边界平行。你需要通过询问来确定这个正方形的位置。每次询问，你可以询问一个多边形与你提问的正方形的相交面积。你最多可以进行 5 次询问。 **输入输出数据格式：** - **输入格式：** 第一行包含两个整数 $ n $ 和 $ m $ ($ 1 \le n, m \le 100 $) — 长方形区域的大小。 - **输出格式：** 为了查询一个有 $ k $ ($ 3 \le k \le 1000 $) 个顶点的多边形与毒害正方形的相交面积，需要打印 $ k+1 $ 行。在第一行打印 "? k"。在接下来的 $ k $ 行中，每行打印两个实数 $ 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} $，则你的答案被认为是正确的。 打印查询后，不要忘记输出换行符并刷新输出。否则，你将得到超时限制。对于不同的语言，使用相应的方法来刷新输出。 - **输入输出样例：** - **输入样例 #1：** ``` 3 3 ``` - **输出样例 #1：** ``` ? 4 0 0 2 0 2 3 0 3 ? 4 0 0 0 1 3 1 3 0 ! 1.5 0.5 ```