P16367 [OOI 2026] Cutting the Cake
题目背景
在提交代码时，不应引入 `triangles.h` 头文件，而是直接将
```cpp
#include
std::vector solve(int n);
struct Triangle {
int i, j, k;
Triangle() = default;
Triangle(int i_, int j_, int k_) : i(i_), j(j_), k(k_) {}
};
int compare(const std::vector& left, const std::vector& right);
```
复制在代码开头。同时，请选择 >=C++17 的语言标准。
题目描述
**本题只能使用 C++ 编程语言解决。**
一次闭门中学生编程竞赛的组织者决定为晚宴订购一个大蛋糕。他们订购了一个带有 $n$ 支蜡烛的蛋糕，蜡烛从 $0$ 到 $n-1$ 编号。已知蜡烛位于平面上的不同点，没有三支蜡烛共线，也没有四支蜡烛构成梯形（即拥有两条平行边的四边形）。
为了确保每个人都能分到蛋糕，组织者希望预先构造一种切割蛋糕的方式，使得切出的块数尽可能多。不幸的是，你并不知道蛋糕上蜡烛的位置，唯一能够了解蛋糕样子的方法是通过电子邮件与糕点店通信。
在一次消息中，你可以请求称量不超过四个以蜡烛为顶点的三角形块：
- 你需要提供两个三角形列表 `left` 和 `right`，两个列表包含的三角形总数不超过四个。这些三角形可以相交、共享公共蜡烛，甚至完全重合。
- 糕点店会按照请求的列表，从蛋糕的多个副本上切下三角形块，并将 `left` 中的块放在天平的左边，`right` 中的块放在天平的右边。
- 你将收到称量的结果。我们认为一块蛋糕的重量等于其面积。你将由此得知哪一个三角形列表的总面积更大，或者两者面积相等。
经过若干次称量后，你必须找出一种切割蛋糕的方法。每块必须是一个以蜡烛为顶点的凸多边形。多边形的顶点必须按照顺时针或逆时针的遍历顺序列出。任意两块不能在内部点处相交。你必须返回一个总面积最大的块列表，此外在某些分组中，还需要在保持总面积最大的前提下最大化块的数量。
### 解决方案格式
这是一道不同寻常的问题。它采用带有交互库的测试格式，你只需要实现函数 `solve` 作为解答。该函数会被裁判程序（交互库）调用，函数的返回值将被接受为问题的解。
具体而言，这意味着你提交的代码 **不得包含输入或输出**。你的代码 **不得** 包含 `main` 函数。如有必要，你可以实现任意数量的辅助函数、结构体、类以及全局变量，但你的全部解答代码必须位于同一个文件中。
你必须实现如下函数：
```cpp
std::vector solve(int n);
```
函数 `solve` 接受一个整数 `n` —— 蜡烛的数量。
在函数 `solve` 的实现中，你可以使用由交互库实现的函数 `compare`：
```cpp
int compare(const std::vector& left, const std::vector& right);
```
该函数接受两个非空的三角形列表，其总大小不超过 $4$。它返回 $-1$，如果 `left` 中三角形的总面积小于 `right` 中三角形的总面积；返回 $0$，如果两者面积相等；否则返回 $1$。如果发出了错误的请求或者超出了请求次数限制，程序将自动终止。
为了在你的解决方案中使用函数 `compare`，你的代码第一行必须包含头文件，加上如下一行：
```cpp
#include "triangles.h"
```
在该头文件中，函数 `compare` 所使用的结构体 `Triangle` 定义如下：
```cpp
struct Triangle {
int i, j, k;
Triangle() = default;
Triangle(int i_, int j_, int k_) : i(i_), j(j_), k(k_) {}
};
```
该结构体描述一个三角形块，其中参数 `i`、`j` 和 `k` 表示构成该三角形块顶点的蜡烛编号。单个三角形块的蜡烛编号必须互不相同，但它们可以在多个三角形中重复出现。
**你不需要在你提交的代码中包含结构体 Triangle 的定义；它将自动来自头文件。**
所有参数（请求中的蜡烛编号，以及你返回的结果中的编号）均采用 **0 基索引**。
你的函数 `solve` 应当通过调用 `compare` 来找出蛋糕的一种划分，划分为若干凸块，任意两块不在内部点相交，块的总面积最大，并且可能的话，块的数量也最大。
函数 `solve` 应当返回一个由蛋糕分块组成的列表。每一块由一个 `std::vector` 描述，包含构成该凸多边形的蜡烛编号。蜡烛编号必须按照 **沿多边形边界的遍历顺序** （顺时针或逆时针）排列。任意两块不得在内部点相交。你必须返回一个总面积最大的块列表，在某些分组中，还要求在保持总面积最大的条件下额外最大化块的数量。
在一次交互库的运行过程中，**裁判会恰好调用一次函数 `solve`**。**交互库不是自适应的**，这意味着蜡烛的位置是事先固定的，不依赖于函数 `solve` 的实现。
### 测试
提供一个解答模板 `triangles.cpp`，以及头文件 `triangles.h`，其中包含函数 `solve` 和 `compare` 的定义。为方便测试，还提供了一个交互库——文件 `grader.cpp`。该文件实现了从标准输入流读取输入数据、调用函数 `solve`、并将函数 `solve` 的结果输出到标准输出流。在评测系统中，交互库可能有所不同。
在 C++ 中编译你的代码 `triangles.cpp`，使用命令
```bash
g++ -std=c++20 grader.cpp triangles.cpp -o grader
```
执行此命令后，将创建交互库的可执行文件 `grader` 或 `grader.exe`（取决于你的操作系统），你可以运行它并输入指定格式的测试数据。
如果通过命令编译遇到困难，对于本地测试，你可以将函数 `solve` 的实现复制到文件 `grader.cpp` 中（必须插入在函数 `main` 之前），然后运行 `grader.cpp`。在这种情况下，在提交解答到测试系统之前，你需要只保留函数 `solve` 的实现，**并切记在代码开头包含头文件**（这通过在提交的代码开头添加一行 `#include "triangles.h"` 实现）。如果你使用了任何 C++ 库，也必须在提交代码的开头包含它们。
如果收到编译错误的判决，请确保 **你所提交的代码不包含 main 函数，也不包含函数 compare 和结构体 Triangle 的定义**。在提交的代码中，你只能使用函数 `compare` 和结构体 `Triangle`。
输入格式
交互库按以下格式读入测试数据：
第一行包含一个整数 $n$（$4 \leq n \leq 10\,000$）—— 蜡烛的数量。
接下来的 $n$ 行，每行包含两个整数 $x_i$, $y_i$（$-10^9 \leq x_i, y_i \leq 10^9$）—— 第 $i$ 支蜡烛的坐标。
输出格式
交互库输出函数 `solve` 的结果——找到的蛋糕分块列表。
第一行输出找到的多边形数量（函数 `solve` 返回的 vector 的大小）。
接下来的行，对于每个多边形（函数 `solve` 返回的 vector 中的一个元素），首先输出该多边形的顶点数，紧接着一行输出作为该多边形顶点的蜡烛编号（即函数 `solve` 返回的每个 `std::vector` 中的元素）。每个多边形必须是凸多边形，且其顶点按遍历顺序（顺时针或逆时针）列出。任意两个多边形不得在内部点相交。
在文件 `grader.cpp` 中，有一个变量 `verbose`，初始值为 $0$。通过增大其值，交互库会输出关于你的解答及其请求的更详细信息。
说明/提示
### 注意
在第一个样例中，可能的函数调用序列如下：
最初，函数 `solve(4)` 被调用。
从函数 `solve` 中，调用了
```cpp
compare({Triangle(0, 1, 2)}, {Triangle(1, 2, 3)})
```
在函数执行过程中，比较了以蜡烛 $0$、$1$、$2$ 为顶点的三角形块和以蜡烛 $1$、$2$、$3$ 为顶点的三角形块的大小。
由于第一个三角形小于第二个，函数返回 $-1$。
接着，从函数 `solve` 中，调用了
```cpp
compare({Triangle(1, 2, 3)}, {Triangle(0, 1, 2), Triangle(0, 1, 3)})
```
响应将返回 $1$，因为以蜡烛 $1$、$2$、$3$ 为顶点的三角形面积大于以蜡烛 $0$、$1$、$2$ 为顶点的三角形和以蜡烛 $0$、$1$、$3$ 为顶点的三角形的总面积。
接下来，从函数 `solve` 中，调用了
```cpp
compare({Triangle(1, 2, 3)}, {Triangle(0, 1, 2), Triangle(2, 3, 0), Triangle(0, 1, 3)})
```
响应将返回 $0$。
最终，函数 `solve` 返回 `{{0, 1, 2}, {0, 2, 3}, {0, 1, 3}}`——这是对蛋糕的一种划分，分为具有最大可能总面积且在内部点不相交的凸多边形。
在第一和第三个样例中，找到的切割方法拥有最大可能的块数，因此在要求最大化的分组中，这样的答案会被认为是正确的。在第二个测试中，块数不是最大可能的，因此在不要求最大化的分组中，这样的答案被认为是正确的，但在要求最大化的分组中，它将获得 $0$ 分。
注意，第一组样例满足分组 $1$ 和 $2$ 的附加限制，而第三组样例满足分组 $5$ 的附加限制。
### 计分
本题的测试数据分为 11 组。各组得分的规则描述如下。注意，某些组不要求通过题面样例。每组的最终得分等于你所有提交的解答中在该组测试上获得的最高分。
一个解答在一组测试上的得分等于该组内所有测试中得分的最小值。
- 如果你的解决方案对 `compare` 进行了错误调用，或返回了不满足强制条件的答案，该测试将获得 $0$ 分。
- 在每个测试中，你的解决方案最多允许调用 $2 \cdot 10^6$ 次 `compare`。如果超出限制，该测试得 $0$ 分。
- 在某些分组中，要求答案最大化块数。在这类分组中，如果块数不是最大可能的，该测试得 $0$ 分。
如果测试中未违反上述任何条件，该测试的答案视为正确。设该测试组的满分为 $p$。某些组采用公式评分，另一些组不采用公式评分：
- 如果该组不采用公式评分，该测试的得分等于 $p$。
- 否则，如果该组采用公式评分，令 $q$ 为你解决方案对 `compare` 的调用次数。则该测试的得分等于
$$\left\lfloor p \cdot \frac{20n}{\max{(q, 20n)}} \right\rfloor$$
| 子任务编号 | 满分 | 评分方式 | < | 附加限制 | 必过组别 | 备注 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| | | 最大 | 公式 | $n$ | | |
| $0$ | $0$ | 否 | 否 | -- | -- | 题面样例 |
| $1$ | $13$ | 否 | 否 | $n = 4$ | -- | |
| $2$ | $4$ | 是 | 否 | $n = 4$ | $1$ | |
| $3$ | $13$ | 否 | 否 | -- | -- | 包含 $(10^9, -10^9)$、$(-10^9, 10^9)$、$(10^9, 10^9)$，其余为该三角形内随机点 |
| $4$ | $8$ | 是 | 否 | -- | $3$ | 包含 $(10^9, -10^9)$、$(-10^9, 10^9)$、$(10^9, 10^9)$，其余为该三角形内随机点 |
| $5$ | $11$ | 是 | 是 | -- | -- | 点为凸多边形的顶点 |
| $6$ | $9$ | 否 | 否 | $n \leq 100$ | -- | 随机点 |
| $7$ | $8$ | 是 | 否 | $n \leq 100$ | $6$ | 随机点 |
| $8$ | $9$ | 否 | 是 | -- | -- | 随机点 |
| $9$ | $8$ | 是 | 是 | -- | -- | 随机点 |
| $10$ | $9$ | 否 | 是 | -- | -- | |
| $11$ | $8$ | 是 | 是 | -- | -- | |
在分组 6–9 中，所有点均独立随机地选自正方形 $[-10^9, 10^9] \times [-10^9, 10^9]$。
在分组 3–4 中，除 $(10^9, -10^9)$、$(-10^9, 10^9)$、$(10^9, 10^9)$ 外的点独立随机地选自以 $(10^9, -10^9)$、$(-10^9, 10^9)$、$(10^9, 10^9)$ 为顶点的三角形。
在这些分组中，仅保留那些满足所有点互异、无三点共线、无四点构成梯形的随机测试数据。
翻译由 DeepSeek V4 Pro 完成