P10735 [NOISG 2019 Prelim] Square or Rectangle?

翻译自 [NOISG2019 Prelim D.Square or Rectangle?](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。 请注意，本题为**交互题**，请**尽量使用 C++ 进行作答**。同时，你**只需要实现题目中要求的函数**。**不要将答案输出在标准输出。** 对于非 C++ 语言的选手，本题有 IO 交互版：，可在此进行评测。

现在有一个 $N\times N$ 的网格，网格内**有一个至少占网格总大小 $4\%$ 的矩形**。但是，你现在不知道这个矩形是长方形还是正方形，你需要**定义一个函数**来完成这个问题。 ### 【实现细节】 你需要定义以下函数： `bool am_i_square(int N, int Q)` - $N$：网格的大小 - $Q$：能询问评测机的次数。 为了确定形状，你可以向评测机至多调用 $Q$ 次 `bool inside_shape(int X, int Y)` 函数。调用这个来询问评测机方格 $(X,Y)$ 是否在这个矩形中。 一旦你确定了形状，你就可以返回一个 `bool` 类型的量，代表这个矩形是否为**正方形**。 评测机会调用你的函数 $T$ 次。$T$ 的大小见【数据范围与评测方法】。

见【实现细节】。

见【实现细节】。

### 【样例】 考虑以下调用：  `am_i_square(5, 25)` 这表示这是一个 $5 \times 5$ 大小的网格，你可以调用至多 $25$ 次。 `inside_shape(3, 3) = true` 这询问了方格 $(3,3)$ 是否在矩形内，它在正方形的正中间，所以返回 `true`。 `inside_shape(5, 4) = false` 这询问了方格 $(5,4)$ 是否在矩形内，它不在正方形内，所以返回 `false`。 `inside_shape(1, 1) = false` 这询问了方格 $(1,1)$ 是否在矩形内，它不在正方形内，所以返回 `false`。 `inside_shape(2, 4) = true` 这询问了方格 $(2,4)$ 是否在矩形内，它在正方形的左下角，所以返回 `true`。 综上，我们可以确定这是一个正方形，所以该函数返回 `true`。 ### 【数据范围与评测方法】 对于 $100\%$ 的测试点：$N=100,1\leq T \leq 1000$。 | $\text{Subtask}$ | 分值 | 附加条件 | | :----------: | :----------: | :----------: | | $0$ | $14$ | $Q=10^4$ | | $1$ | $19$ | $Q=100$ | | $2$ | $18$ | $Q=40$，图形至少占网格总大小的 $25\%$ | | $3$ | $49$ | $Q=50$，得分见下文 | ### 【Subtask 3 的计分方法】 记你在所有调用中最大使用了 $q$ 次询问。 - 若 $q >50$，你得到 $0$ 分。 - 若 $34 \leq q \leq 50$，你得到 $40-30\times \frac{q-34}{17}$ 的分数。 - 若 $q \leq 33$，你得到满分。 ### 【提示】 请在你的函数前加上以下内容： ```cpp #include using namespace std; extern "C" bool inside_shape(int x,int y); ``` 同时，请在你的 `bool am_i_square(int N, int Q)` 前加上`extern "C" `。