题解

思路

把面积统一乘二后，所有运算都可以使用整数叉积。一个被选多边形合法，当且仅当它是凸多边形，并且没有未选点位于其内部。

固定多边形在某个方向上的最左顶点 $O$。其余可能入选的顶点都在 $O$ 的右侧，并可按绕 $O$ 的极角排序。合法凸多边形从 $O$ 出发后按这个顺序选点，最后再回到 $O$。关键是判断两个候选点之间能否作为相邻边：如果它们之间的扇形区域包含必须落入多边形内部的点，这条边就不可见；反之可以连接。

对所有可见有向边建立图后，按照边方向的极角扫描。状态 $dp[c][v]$ 表示已经选了 $c$ 个顶点、最后一个顶点为 $v$ 时，当前扇形面积和的最大值。经过边 $u\to v$ 时增加叉积 $\operatorname{cross}(O,u,v)$；当选满 $K$ 个点并遇到回到 $O$ 的闭合事件时更新答案。

为了消除竖直方向带来的极角断点，可以先做一个行列式为 $1$ 的整数线性变换，例如

这个变换保持叉积与面积不变，并保证不同输入点的第一坐标互不相同，因此每个固定根的候选点都严格位于其右侧。

做法

子任务 1 枚举所有大小为 $K$ 的点集。对每个集合求凸包，要求凸包恰有 $K$ 个顶点，再检查所有未选点都不在凸包内部，最后计算面积取最大值。

子任务 2 对每个根 $O$ 极角排序其右侧点。枚举候选边 $i\to j$，直接扫描极角位于二者之间的全部点；若其中存在点位于有向边左侧，则这条边会把该点包入当前扇形，不能作为空凸多边形的边。得到全部可见边后执行极角事件动态规划。

满分做法需要更快地建立可见边。对每个极角位置维护一个队列。初始递归处理相邻点对 $(i,i+1)$。处理 $(i,j)$ 时，只要队列 $Q_i$ 的队首前驱 $u$ 与当前方向形成左转，就先递归处理 $(u,j)$ 并弹出队首；随后加入边 $(i,j)$，并把 $i$ 压入 $Q_j$。每个有序三角关系只在递归中被处理有限次，从而在每个根下以二次规模建立可见图。

边建立完成后，把三类事件统一按方向极角排序：从根出发、候选点之间转移、回到根。相同方向时按这三类顺序处理，保证零夹角边界的状态依赖正确。按事件顺序执行上述 $K$ 层动态规划即可。

正确性证明

固定根后，任意包含该根的凸多边形，其余顶点按绕根极角严格递增。若相邻顶点之间存在一个候选点落在对应有向边左侧，那么该点严格位于多边形内部，方案非法；反之，每一条相邻边都通过可见性检查时，各扇形内部都没有未选点，整个凸多边形内部也没有未选点。因此可见图中的闭合路径与以该根为最左点的合法方案一一对应。

递归队列算法维护每个终点的候选前驱下包络。发生左转时，队首前驱已经不可能跨过当前点继续保持可见，递归生成它与新终点之间应出现的边后即可永久弹出；没有左转时，现有前驱仍按可见顺序保留。由极角顺序归纳，算法生成且只生成上述可见边。

事件动态规划按照每条边的方向顺序扩展路径。转移加入的叉积恰好是三角形 $(O,u,v)$ 的两倍有向面积；凸路径的这些三角形互不重叠，其和等于多边形两倍面积。枚举所有可能的最左根后，所有合法多边形都会被考虑，因此得到全局最大面积。

复杂度

子任务 1 的时间复杂度为 $O\!\left(\binom{N}{K}N K\right)$，空间复杂度为 $O(N)$。

子任务 2 的时间复杂度为 $O(N^4+KN^3)$，空间复杂度为 $O(KN+N^2)$。

满分做法的时间复杂度为 $O(KN^3)$，空间复杂度为 $O(KN+N^2)$。