luogu#P10735. [NOISG2019 Prelim] Square or Rectangle?
[NOISG2019 Prelim] Square or Rectangle?
题目背景
翻译自 NOISG2019 Prelim D.Square or Rectangle?。
请注意,本题为交互题,请尽量使用 C++ 进行作答。同时,你只需要实现题目中要求的函数。不要将答案输出在标准输出。
题目描述
现在有一个 的网格,网格内有一个至少占网格总大小 的矩形。但是,你现在不知道这个矩形是长方形还是正方形,你需要定义一个函数来完成这个问题。
【实现细节】
你需要定义以下函数:
bool am_i_square(int N, int Q)
- :网格的大小
- :能询问评测机的次数。
为了确定形状,你可以向评测机至多调用 次 bool inside_shape(int X, int Y)
函数。调用这个来询问评测机方格 是否在这个矩形中。
一旦你确定了形状,你就可以返回一个 bool
类型的量,代表这个矩形是否为正方形。
评测机会调用你的函数 次。 的大小见【数据范围与评测方法】。
输入格式
见【实现细节】。
输出格式
见【实现细节】。
提示
【样例】
考虑以下调用:
am_i_square(5, 25)
这表示这是一个 大小的网格,你可以调用至多 次。
inside_shape(3, 3) = true
这询问了方格 是否在矩形内,它在正方形的正中间,所以返回 true
。
inside_shape(5, 4) = false
这询问了方格 是否在矩形内,它不在正方形内,所以返回 false
。
inside_shape(1, 1) = false
这询问了方格 是否在矩形内,它不在正方形内,所以返回 false
。
inside_shape(2, 4) = true
这询问了方格 是否在矩形内,它在正方形的左下角,所以返回 true
。
综上,我们可以确定这是一个正方形,所以该函数返回 true
。
【数据范围与评测方法】
对于 的测试点:。 | | 分值 | 附加条件 | | :----------: | :----------: | :----------: | | | | | | | | | | | | ,图形至少占网格总大小的 | | | | ,得分见下文 |
【Subtask 3 的计分方法】
记你在所有调用中最大使用了 次询问。
- 若 ,你得到 分。
- 若 ,你得到 的分数。
- 若 ,你得到满分。
【提示】
请在你的函数前加上以下内容:
#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"
。