bzoj#P4858. [JSOI2016]炸弹攻击 2

[JSOI2016]炸弹攻击 2

题目背景

还记得那款题为炸弹攻击的塔防游戏吗?这款游戏出了续作,炸弹的威力大大加强了。

题目描述

游戏的地图是一个二维平面。JYY 的阵地位于xx轴下方,而所有的敌人目前都位于xx轴上方。

在 JYY 的阵地中有建有TT个激光塔和SS个发射源。其中第ii个防御塔TiT_i的坐标为(txi,tyi)(tx_i,ty_i),第ii个发射源SiS_i的坐标为(sxi,syi)(sx_i,sy_i)

地图上有DD个敌人,第ii个敌人DiD_i的坐标为(dxi,dyi)(dx_i,dy_i)

两座激光塔可以相互连接形成能量墙。发射源朝向敌人发出的能量如果穿过了能量墙,可以得到巨大的加强而变为超级射线并瞬间消灭敌人。

JYY 想知道他有多少种可以可以发出超级射线的攻击方案。

具体来说,一个可以发出超级射线的攻击方案为一个由四个点组成的集合:{Ti,Tj,Sk,DlT_i,T_j,S_k,D_l},满足11\leqii<<jj\leqTT,,11\leqkk\leqSS,,11\leqll\leqDD,并且线段TiTjT_iT_j和线段SkDlS_kD_l相交。

游戏设定保证在这TT++DD++SS个点中,不存在重点也不存在三点共线。

输入格式

第一行包含一个正整数DD

接下来DD行,每行包含两个整数dxi,dyidx_i,dy_i,表示一个敌人的坐标;

DD++11行包含一个整数SS

接下来SS行,每行包含两个整数sxi,syisx_i,sy_i,表示一个发射源的坐标;

DD++SS++11行包含一个整数TT

接下来TT行,每行包含两个整数(txi,tyi)(tx_i,ty_i),表示一个激光塔的坐标。

输出格式

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

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

提示

对于2020%的数据,满足D,S,TD,S,T\leq3030

对于5050%的数据,满足D,S,TD,S,T\leq150150

对于100100%的数据,满足11\leqD,S,TD,S,T\leq800800,,dyidy_i>>00,,syisy_i,,tyity_i<<00,所有坐标绝对值不超过10910^9