Square or Rectangle?

题目描述

本题是函数式交互 / Grader 题。

有一个由 $N\times N$ 个小方格组成的网格。现在有一个图形覆盖了其中若干个小方格。这个图形保证是一个正方形或一个矩形，并且图形边界都沿着网格线，也就是说每个小方格要么完全在图形内部，要么完全在图形外部。

图形覆盖的面积保证至少占整个网格面积的 $4\%$。

你的任务是判断这个图形是正方形还是矩形。

你最多可以询问 $Q$ 次。每次询问一个小方格坐标 $(X,Y)$，评测程序会告诉你该小方格是否在图形内部。

网格坐标满足：

$$1\le X,Y\le N.$$

实现要求

选手需要提交一个 C++ 源文件，并包含头文件：

#include "squarerect.h"

你需要实现函数：

bool am_i_square(int N, int Q);

函数 am_i_square 会被调用至多 $T$ 次。每一次调用代表一个独立的测试实例，图形可能不同，并且在这一次调用中最多允许询问 $Q$ 次。

如果你认为当前图形是正方形，应返回 true；否则返回 false。

在 am_i_square 中，你可以调用以下函数进行询问：

bool inside_shape(int X, int Y);

若小方格 $(X,Y)$ 在图形内部，inside_shape 返回 true；否则返回 false。

如果调用 inside_shape 的次数超过 $Q$，或者询问坐标不满足 $1\le X,Y\le N$，程序会立即被判为错误。

重要说明

本题不是普通标准输入输出题。

选手程序中：

• 不要读标准输入；
• 不要向标准输出输出内容；
• 不要编写 main 函数；
• 只需要实现 am_i_square 函数。

提交代码模板如下：

#include "squarerect.h"
#include <bits/stdc++.h>
using namespace std;

bool am_i_square(int N, int Q) {
    // 在这里实现你的算法。
}

评测用输入格式说明

正式评测时，输入由评测主程序读取，选手不需要处理。

本地测试用输入格式如下：

第一行包含三个整数：

$$T,N,Q.$$

接下来 $T$ 行，每行包含四个整数：

$$X_1,Y_1,X_2,Y_2,$$

表示图形左上角为 $(X_1,Y_1)$，右下角为 $(X_2,Y_2)$。

若：

$$X_2-X_1=Y_2-Y_1,$$

则图形是正方形；否则是矩形。

样例交互说明

假设 $N=5,Q=25$，并且当前图形是一个正方形。

一次可能的交互过程如下：

inside_shape(3, 3) = true
inside_shape(5, 4) = false
inside_shape(1, 1) = false
inside_shape(2, 4) = true

当程序认为已经获得足够信息后，可以返回 true，表示判断该图形是正方形。

数据范围

对于所有测试数据：

$$N=100,$$ $$1\le T\le 1000.$$

各子任务限制如下：

子任务	分值	限制
1	14	$Q=10^4$
2	19	$Q=100$
3	18	$Q=40$，图形覆盖面积至少为整个网格的 $25\%$
4	49	$Q=50$，特殊计分

特殊计分

第 4 个子任务为特殊计分子任务。设你的程序在任意一次 am_i_square 调用中使用的最大询问次数为 $q$。

• 若 $q>50$，得 $0$ 分；
• 若 $34\le q\le 50$，得分为：

$$40-30\times\frac{q-34}{17};$$

• 若 $q\le 33$，得到该子任务满分 $49$ 分。

本地测试说明

下发文件包含本地测试用 grader.cpp、squarerect.h、提交模板和运行脚本。

在 Linux/macOS 环境下，可以进入 down/cpp/ 后运行：

chmod +x compile_cpp.sh run_cpp.sh
./compile_cpp.sh
./run_cpp.sh < ../samples/sample.1.in

其中 squarerect.cpp 是选手本地调试用的代码文件。

注意：本地测试脚本仅用于调试公开样例。正式提交时，只需要提交实现了 am_i_square 的 C++ 源代码，评测系统会自动提供正式 grader 和头文件。

@下发文件