P10735 [NOISG 2019 Prelim] Square or Rectangle?

Translated from [NOISG2019 Prelim D.Square or Rectangle?](https://github.com/noisg/sg_noi_archive/blob/master/2019_prelim/)。 Please note that this problem is **interactive**. Please **try to use C++ to solve it**. Also, you **only need to implement the function required in the statement**. **Do not output your answer to standard output.** For contestants using non-C++ languages, there is an interactive I/O version: , where you can submit for evaluation.

You are given an $N \times N$ grid. Inside the grid, there is **one rectangle that occupies at least $4\%$ of the total grid area**. However, you do not know whether this rectangle is a rectangle (non-square) or a square. You need to **define a function** to solve this problem. ### Implementation Details You need to define the following function: `bool am_i_square(int N, int Q)` - $N$: the size of the grid. - $Q$: the number of queries you are allowed to ask the judge. To determine the shape, you may call the judge function `bool inside_shape(int X, int Y)` at most $Q$ times. Call it to ask whether cell $(X, Y)$ is inside the rectangle. Once you have determined the shape, you can return a `bool` value indicating whether the rectangle is a **square**. The judge will call your function $T$ times. The value of $T$ can be found in **Constraints and Scoring**.

See **Implementation Details**.

See **Implementation Details**.

### Sample Consider the following calls:  `am_i_square(5, 25)` This means the grid size is $5 \times 5$, and you may call `inside_shape` at most $25$ times. `inside_shape(3, 3) = true` This asks whether cell $(3, 3)$ is inside the rectangle. It is at the center of the square, so it returns `true`. `inside_shape(5, 4) = false` This asks whether cell $(5, 4)$ is inside the rectangle. It is not inside the square, so it returns `false`. `inside_shape(1, 1) = false` This asks whether cell $(1, 1)$ is inside the rectangle. It is not inside the square, so it returns `false`. `inside_shape(2, 4) = true` This asks whether cell $(2, 4)$ is inside the rectangle. It is at the bottom-left corner of the square, so it returns `true`. Therefore, we can determine that it is a square, so the function returns `true`. ### Constraints and Scoring For $100\%$ of the testdata: $N = 100$, $1 \leq T \leq 1000$. | $\text{Subtask}$ | Points | Additional Constraints | | :----------: | :----------: | :----------: | | $0$ | $14$ | $Q = 10^4$ | | $1$ | $19$ | $Q = 100$ | | $2$ | $18$ | $Q = 40$, the shape occupies at least $25\%$ of the total grid area | | $3$ | $49$ | $Q = 50$, scoring is described below | ### Scoring for Subtask 3 Let $q$ be the maximum number of queries you used among all calls. - If $q > 50$, you get $0$ points. - If $34 \leq q \leq 50$, you get $40 - 30 \times \frac{q - 34}{17}$ points. - If $q \leq 33$, you get full points. ### Notes Please add the following before your function: ```cpp #include using namespace std; extern "C" bool inside_shape(int x,int y); ``` Also, add `extern "C" ` before your `bool am_i_square(int N, int Q)`. Translated by ChatGPT 5