#P13795. TC12156 Ear

    ID: 12996 传统题 2000ms 256MiB 尝试: 26 已通过: 9 难度: 6 上传者: 标签>CF2000计算几何枚举排序前缀和二分数学组合数学

TC12156 Ear

Ear(耳朵)

平面上有一些红点和蓝点。

  • 所有红点都在 xx 轴上:红点坐标为 (x,0)(x,0)
  • 所有蓝点都在上半平面:蓝点坐标为 (x,y)(x,y)y>0y>0

从红点中选出 4 个互不相同的点 A,B,C,DA,B,C,D,从蓝点中选出 2 个互不相同的点 P,QP,Q。如果它们满足下面所有条件,则称这 6 个点组成一个 ear(耳朵)

  1. BBCC 都在 线段 ADAD 的内部(严格在内部,不允许在端点上)。
    由于红点都在 xx 轴上,这等价于:B,CB,Cxx 坐标严格介于 AADDxx 坐标之间。
  2. 四个角 PAD,PDA,QBC,QCB \angle PAD,\angle PDA,\angle QBC,\angle QCB严格小于 9090^\circ
  3. QQ三角形 PADPAD 的内部(严格在内部,不允许在边界上)。

这里 XYZ\angle XYZ 表示以点 YY 为顶点、由射线 YXYXYZYZ 形成的夹角。

你需要计算:能组成 ear 的选点方案数。

注意:只要选到的 6 个点集合相同,就认为是同一个 ear;也就是说 点的顺序不计
(这是原题的说明:不同排列不算不同方案。)

输入格式

  • 第 1 行:整数 nn,红点个数
  • 第 2 行:nn 个整数 redX[1..n]redX[1..n]
  • 第 3 行:整数 mm,蓝点个数
  • 第 4 行:mm 个整数 blueX[1..m]blueX[1..m]
  • 第 5 行:mm 个整数 blueY[1..m]blueY[1..m]

输出格式

输出一个整数,表示 ear 的数量。

9
1 2 3 4 5 6 7 8 9
5
4 5 6 7 8
1 2 3 4 5
204

数据范围(来自原题约束)

  • 1n3001 \le n \le 300
  • 1m3001 \le m \le 300
  • 每个坐标整数都在 [1,10000][1, 10000]
  • redX 内部互不相同;blueX 内部互不相同;blueY 内部互不相同
  • blueXblueY 的长度相同
  • 答案用 64 位整数(long long)保存