[NOISG2019 Prelim] Square or Rectangle?

题目背景

翻译自 NOISG2019 Prelim D.Square or Rectangle?。

请注意，本题为交互题，请尽量使用 C++ 进行作答。同时，你只需要实现题目中要求的函数。不要将答案输出在标准输出。

题目描述

现在有一个 $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$，你得到满分。

【提示】

请在你的函数前加上以下内容：

#include <bits/stdc++.h>
using namespace std;
extern "C" bool inside_shape(int x,int y);

同时，请在你的 bool am_i_square(int N, int Q) 前加上extern "C" 。