#P11185. [NHSPC 2023] D. 共同子凸包
[NHSPC 2023] D. 共同子凸包
题目描述
在数学上,一个点集合 的凸包 (convex hull) 定义为包含 的最小凸集合,记作 。在平面上,若 为非空有限点集合,则 为一包含内部与边界的最小凸多边形,或其退化形式。另一方面,设 与 为平面上的两个点集合。若存在某个二维向量 ,满足
则称 与 经过平移后重合。
现给定平面上的有限点集合 与 ,并考虑它们的非空子集合 与 。已知子凸包 与子凸包 面积皆大于 且经过平移后重合,请求出 所有可能的面积。
以下展示两个子凸包平移后重合的例子。

输入格式
- 代表 的集合大小。
- 代表 的集合大小。
- 代表 包含点 。
- 代表 包含点 。
输出格式
样例输入1
6 5
0 2
1 1
1 3
2 3
3 2
4 2
2 0
2 1
2 2
3 1
5 1
样例输出1
1
6
- 代表若子凸包 与子凸包 经过平移后重合, 所有可能的非 面积数。
- 为一整数,代表 所有可能的非 面积中,第 小的数的两倍。
说明/提示
测试数据限制
- 。
- 。
- 。
- 。
- 。
- 。
- 对任意 ,若 ,则 。
- 对任意 ,若 ,则 。
- 输入的数皆为整数。
评分说明
本题共有四组子任务,条件限制如下所示。 每一组可有一或多个测试数据,该组所有测试数据皆需答对才可获得该组分数。
| 子任务 | 分数 | 额外输入限制 |
|---|---|---|
| 1 | 所有可能的非 面积必能从 与 中各选 个点得到 | |
| 2 | ||
| 3 | ||
| 4 | 无额外限制 |