[JSOI2016]炸弹攻击 2
题号:NC20228
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

还记得那款题为“炸弹攻击”的塔防游戏吗?这款游戏出了续作,炸弹的威力大大加强了。
游戏的地图是一个 2 维平面。JYY 的阵地位于 x 轴下方,而所有的敌人目前 都位于 x 轴上方。
在 JYY 的阵地中有建有 T 个激光塔和 S 个发射源。其中第 i 个防御塔Ti的坐标为(txi,tyi),第 i 个发射源Si的坐标为(sxi,syi)。
地图上有 D 个敌人,第 i 个敌人Di的坐标为(dxi,dyi)。
两座激光塔可以相互连接形成能量墙。发射源朝向敌人发出的能量如果穿过了能量墙,可以得到巨大的加强而变为“超级射线”并瞬间消灭敌人。
JYY 想知道他有多少种可以可以发出超级射线的攻击方案。
具体来说,一个可以发出超级射线的攻击方案为一个由四个点组成的集合:
{Ti,Tj,Sk,Dt},满足1 ≤ i < j < T, 1 ≤ k ≤ S, 1 ≤ l ≤ D 并且线段TiTj和线段Sk,Dl 相交。
游戏设定保证在这T + D + S个点中,不存在重点也不存在三点共线。

输入描述:

第一行包含一个正整数 D。
接下来 D 行,每行包含两个整数(dx, dyi)(dyi > 0),表示一个敌人的坐标。
第 D+1 行包含一个整数 S。
接下来 S 行,每行包含两个整数(sx, syi) (syi < 0),表示一个发射源的坐标。
第 D+S+2 行包含一个整数 T。
接下来 T 行,每行包含两个整数(tx, tyi) (tyi < 0),表示一个激光塔的坐标。

输出描述:

输出一行一个整数,可以发出超级射线的攻击方案个数。
示例1

输入

复制
3
1 12
10 30
30 10
1
10 -10
4
2 -11
9 -1
11 -1
15 -14

输出

复制
7

备注:

对于20%的数据,满足
对于50%的数据,满足
对于100%的数据,满足,所有坐标绝对值不超过