AdditionalFile5737.zip

#5737. 「OOI 2026 Day2」切蛋糕

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2026 Day2 T1 「Разрезание торта」 / 「Cutting the Cake」。

本题仅支持使用 C++ 语言进行评测。

Closed Olympiad 的组织者为晚宴订购了一个大蛋糕。为此，他们准备了一个带有 $n$ 根蜡烛的蛋糕，蜡烛编号为 $0$ 到 $n-1$。已知蜡烛位于平面上的不同点，且满足任意三根蜡烛不共线，任意四根蜡烛不构成梯形（即没有两边平行的四边形）。

为了让每个人都能分到蛋糕，组织者希望预先设计一种将蛋糕切成尽可能多块的方法。遗憾的是，你并不知道蜡烛的具体位置，获取蛋糕信息的唯一途径是通过电子邮件与甜品店沟通。

在单次沟通中，你最多可以请求称量四个由蜡烛作为顶点的三角形小块的重量：

• 你需要提供两个三角形列表 left 和 right，两列表包含的三角形总数不得超过 $4$ 个。这些三角形可以相互重叠、共用蜡烛顶点，甚至可以完全相同。
• 甜品店会根据请求，从几块相同的蛋糕中切出对应的三角形小块。他们会将 left 列表中的三角形放在天平左盘，将 right 列表中的三角形放在天平右盘。
• 甜品店会返回称量结果。我们认为一个小块的重量等于其面积。通过称量，你可以得知哪个列表的三角形总面积更大，或者两者的总面积相等。

在进行若干次称量后，你必须找到一种切蛋糕的方法。每一块蛋糕都必须是以蜡烛为顶点的凸多边形。多边形的顶点必须按顺时针或逆时针方向列出。任意两块蛋糕的内部不得有交集。你返回的蛋糕块列表必须使得它们的总面积尽可能大。此外，在某些子任务中，还要求最大化蛋糕的块数。

实现细节

这是一道交互题。你需要实现一个函数 solve 来完成任务。该函数将由示例评测程序（grader）调用，其返回值将作为该题的解答。

这意味着你提交的代码中不应包含任何输入或输出操作，也不应包含 main 函数。如果需要，你可以实现任意数量的辅助函数、结构体、类和全局变量，但所有的代码必须位于同一个文件中。

你必须实现以下函数：

std::vector<std::vector<int>> solve(int n);

函数 solve 接收一个参数 $n$，表示蜡烛的数量。 在实现 solve 函数时，你可以调用示例评测程序提供的 compare 函数：

int compare(const std::vector<Triangle>& left, const std::vector<Triangle>& right);

该函数接收两个非空的三角形列表，列表中的三角形总数不超过 $4$。

• 如果 left 中三角形的总面积小于 right 中三角形的总面积，函数返回 $-1$；
• 如果两者面积相等，返回 $0$；
• 如果 left 的总面积更大，返回 $1$。

在发出非法请求或超过查询次数限制的情况下，程序将自动终止。

为了在代码中访问 compare 函数，你需要在代码的第一行包含头文件：

#include "triangles.h"

在该头文件中还定义了 Triangle 结构体：

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<std::vector<int>>。其中每个内部向量 std::vector<int> 描述一个凸多边形块，包含按边界顺序（顺时针或逆时针）排列的顶点（蜡烛）编号。

在评测时，示例评测程序只会调用一次 solve 函数。示例评测程序是非适应性的，即蜡烛的位置在程序运行前已经确定，不会根据你的查询而改变。

本地测试

题目提供了模板文件 triangles.cpp 和头文件 triangles.h。为了方便测试，还提供了 grader.cpp 文件。该文件负责从标准输入读取数据、运行 solve 函数并将结果输出到标准输出。在正式评测系统中，评测程序可能与此有所不同。

在本地环境下，你可以使用以下命令编译代码： g++ -std=c++20 grader.cpp triangles.cpp -o grader

编译成功后会生成可执行文件 grader（或 grader.exe），运行它并按照后文所述的格式输入测试数据。

如果你在命令行编译时遇到困难，也可以将 solve 函数的实现直接复制到 grader.cpp 中（放在 main 函数之前）运行。但在提交到系统时，请只保留 solve 函数及其必要的头文件和辅助代码，并确保开头有 #include "triangles.h"。

如果收到编译错误提示，请检查提交的代码中是否包含了 main 函数、compare 函数的定义或 Triangle 结构体的定义。你只能使用它们。

输入格式

示例评测程序按以下格式读取数据：

第一行包含一个整数 $n$ $(4 \leq n \leq 10000)$，表示蜡烛的数量。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ $(-10^9 \leq x_i, y_i \leq 10^9)$，表示第 $i$ 根蜡烛的坐标。

输出格式

示例评测程序会输出 solve 函数的返回结果：

第一行输出多边形的数量（即返回向量的大小）。

接下来的每一行，首先输出该多边形的顶点数，随后在其后一行输出作为该多边形顶点的蜡烛编号。

在 grader.cpp 文件中有一个变量 verbose，初始值为 $0$。如果你调大该值，示例评测程序会输出更详细的查询信息。

样例 1

输入

4
1 2
1 4
0 0
3 -1

输出

3
3
0 1 2
3
0 2 3
3
0 1 3

在第一个样例中，一种可能的函数调用序列如下：

首先，调用 solve(4)。

在 solve 内部调用：

compare({Triangle(0, 1, 2)}, {Triangle(1, 2, 3)})

此时会比较由蜡烛 $0, 1, 2$ 构成的三角形与蜡烛 $1, 2, 3$ 构成的三角形的面积。

由于第一个三角形面积较小，函数返回 $-1$。 随后调用：

compare({Triangle(1, 2, 3)}, {Triangle(0, 1, 2), Triangle(0, 1, 3)})

返回 $1$，因为三角形 $(1, 2, 3)$ 的面积大于三角形 $(0, 1, 2)$ 和 $(0, 1, 3)$ 的总面积。

随后调用：

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}}，这是一种不相交且总面积最大的分割方案。

此样例满足子任务 $1, 2$ 的限制。

样例 2

输入

5
-1 -1
4 4
4 -2
1 2
-2 2

输出

1
4
0 4 1 2

样例 3

输入

6
2 2
0 -2
-1 3
-2 0
7 0
2 -3

输出

4
3
2 4 3
3
3 4 5
3
1 3 5
3
0 2 4

在第一个和第三个样例中，所给方案的蛋糕块数已经达到最大值，因此在要求最大化块数的子任务中也是正确的。在第二个样例中，块数并非最大，因此虽然在普通子任务中正确，但在要求最大化块数的子任务中会得到 $0$ 分。

此样例满足子任务 $5$ 的限制。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

• 在做出非法 compare 调用或返回不符合基本条件的方案的情况下，该测试点得 $0$ 分。
• 每个测试点最多允许调用 $2 \cdot 10^6$ 次 compare 函数，在超出限制的情况下，该测试点得 $0$ 分。
• 在要求最大化块数的子任务中，如果返回的块数不是该测试点可能的最大值，该测试点得 $0$ 分。

在不违反上述条件的情况下，答案被视为正确。设某组子任务的总分为 $p$：

• 如果该组不使用评分公式，则得分为 $p$。
• 在使用评分公式的情况下，设 $q$ 为你的程序调用 compare 的次数，得分按公式计算为 $\lfloor p \cdot \frac{20 n}{\max(q, 20 n)} \rfloor$。

子任务	分值	最大化块数	评分公式	附加限制	子任务依赖
$1$	$13$	否	否	$n=4$	-
$2$	$4$	是			$1$
$3$	$13$	否		包含三个特定顶点，其余点在三角形内随机	-
$4$	$8$	是			$3$
$5$	$11$		是	蜡烛构成凸多边形的所有顶点	-
$6$	$9$	否	否	$n \leq 100$，点随机生成
$7$	$8$	是			$6$
$8$	$9$	否	是	点随机生成	-
$9$	$8$	是
$10$	$9$	否		无附加限制
$11$	$8$	是

子任务 $3-4$ 中的特定顶点坐标为 $(10^9, -10^9), (-10^9, 10^9), (10^9, 10^9)$。其余点在以此为顶点的三角形内独立均匀随机生成。

子任务 $6-9$ 中的点在正方形区域 $[-10^9, 10^9] \times [-10^9, 10^9]$ 内独立均匀随机生成。

在这些随机生成的测试点中，系统已剔除了包含重复点、三点共线或四点构成梯形的情况。