#P5545. [JSOI2016] 炸弹攻击2

    ID: 4533 Type: RemoteJudge 2000ms 500MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>计算几何2016各省省选江苏

[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,Dl}\{T_i,T_j,S_k,D_l\},满足$1 \leq i < j \leq T,1 \leq k \leq S,1 \leq l \leq D$,并且线段 TiTjT_iT_j 和线段 SkDlS_kD_l 相交。

游戏设定保证在这 T+D+ST+D+S 个点中,不存在重点也不存在三点共线。

输入格式

第一行包含一个正整数 DD

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

D+1D+1 行包含一个整数 SS

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

D+S+1D+S+1 行包含一个整数 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

提示

对于 20%20\% 的数据,满足 D,S,T30D,S,T \leq 30

对于50%50\% 的数据,满足 D,S,T150D,S,T \leq 150

对于100%100\% 的数据,满足 1D,S,T800,dyi>0,syi,tyi<01 \leq D,S,T \leq 800 , dy_i>0,sy_i,ty_i<0,所有坐标绝对值不超过 10910^9