#P13795. TC12156 Ear
TC12156 Ear
Ear(耳朵)
平面上有一些红点和蓝点。
- 所有红点都在 轴上:红点坐标为 。
- 所有蓝点都在上半平面:蓝点坐标为 且 。
从红点中选出 4 个互不相同的点 ,从蓝点中选出 2 个互不相同的点 。如果它们满足下面所有条件,则称这 6 个点组成一个 ear(耳朵):
- 和 都在 线段 的内部(严格在内部,不允许在端点上)。
由于红点都在 轴上,这等价于: 的 坐标严格介于 与 的 坐标之间。 - 四个角 都 严格小于 。
- 点 在 三角形 的内部(严格在内部,不允许在边界上)。
这里 表示以点 为顶点、由射线 与 形成的夹角。

你需要计算:能组成 ear 的选点方案数。
注意:只要选到的 6 个点集合相同,就认为是同一个 ear;也就是说 点的顺序不计。
(这是原题的说明:不同排列不算不同方案。)
输入格式
- 第 1 行:整数 ,红点个数
- 第 2 行: 个整数
- 第 3 行:整数 ,蓝点个数
- 第 4 行: 个整数
- 第 5 行: 个整数
输出格式
输出一个整数,表示 ear 的数量。
9
1 2 3 4 5 6 7 8 9
5
4 5 6 7 8
1 2 3 4 5
204
数据范围(来自原题约束)
- 每个坐标整数都在
redX内部互不相同;blueX内部互不相同;blueY内部互不相同blueX与blueY的长度相同- 答案用 64 位整数(
long long)保存
相关
在以下作业中: