题解

以下所有面积均指真实面积的两倍，因此全程只需使用整数。

思路

小规模直接枚举所有不交对角线集合；更大规模二分最小面积，并对环上的连续顶点区间做动态规划。满分算法再利用凸多边形面积的单调性，以双指针优化内部区间转移。

做法

子任务 1：枚举不交对角线集合

当 $n\le 8$ 时，候选对角线不超过 $20$ 条。枚举恰含 $k$ 条对角线的子集，检查任意两条是否在内部相交；对合法子集沿平面图的有向边枚举所有内部面，取其中最小面积并更新答案。

这一算法直接枚举所有切割方案，复杂度为 $O(2^{n(n-3)/2}\cdot n^2)$。

二分答案

设当前判定阈值为 $w$。我们只需判断能否把多边形分成至少 $k+1$ 个、两倍面积均不小于 $w$ 的区域。若可行，更小的阈值也一定可行，因此可以二分答案。

把顶点序列复制一遍，以普通区间表示环上的任意连续顶点段。记 $S(l,r)$ 为顶点 $l,l+1,\ldots,r$ 与弦 $(r,l)$ 围成的多边形的两倍面积。鞋带公式可在 $O(n^2)$ 时间预处理所有 $S(l,r)$。

区间状态

固定 $w$，令 $dp(l,r)$ 表示子多边形 $[l,r]$ 内最多能完整切出的、面积至少为 $w$ 的区域数。按照区间长度从小到大转移。

任意合法切割的对偶图是一棵树。可以证明：若存在合法切割，则存在一种合法切割，使每个区域在对偶树中的度数不超过 $3$。因此只需考虑以下三种结构。

1. 丢弃一个端点：

   $$dp(l,r)\gets\max\{dp(l+1,r),dp(l,r-1)\}.$$

2. 区域以三角形 $(l,m,r)$ 连接左右两部分。若

   $$[p_l,p_m,p_r]\ge w,$$

   则

   $$dp(l,r)\gets\max\bigl(dp(l,r),dp(l,m)+dp(m,r)+1\bigr).$$

3. 新区域包围一个连续的内部子多边形 $[a,b]$。该新区域的面积为

   $$S(l,r)-S(a,b).$$

   若它不小于 $w$，则

   $$dp(l,r)\gets\max\bigl(dp(l,r),dp(a,b)+1\bigr).$$

最后枚举一条分割弦 $(l,r)$。其两侧对应 $[l,r]$ 与环状区间 $[r,l+n]$，当

时，阈值 $w$ 可行。

子任务 2：直接枚举内部区间

对第三类转移直接枚举 $a,b$，一次判定为 $O(n^4)$，配合二分后为 $O(n^4\log A)$，其中 $A$ 是多边形的两倍面积。该算法通过 $n\le 32$ 的数据。

子任务 3：单调双指针

对固定的 $(l,r)$ 和 $a$，条件为

随着 $b$ 增大，$S(a,b)$ 单调不减；随着 $a$ 增大，满足条件的最大 $b$ 也不会减小。并且 $dp(a,b)$ 对 $b$ 单调不减，所以只需取满足面积条件的最大 $b$。用一个不回退的指针即可在线性时间完成当前 $(l,r)$ 的全部第三类转移。

每个区间的三类转移共需 $O(n)$，一次判定为 $O(n^3)$，总复杂度为 $O(n^3\log A)$，空间复杂度为 $O(n^2)$。

坐标乘积和面积可能达到 $10^{16}$ 量级，必须使用 64 位整数。

复杂度

• 子任务 1：$O(2^{n(n-3)/2}\cdot n^2)$ 时间，$O(n^2)$ 空间；
• 子任务 2：$O(n^4\log A)$ 时间，$O(n^2)$ 空间；
• 满分算法：$O(n^3\log A)$ 时间，$O(n^2)$ 空间。