A91999.「JSOI2016」炸弹攻击 2
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:512MB
题目描述
还记得那款题为「炸弹攻击」的塔防游戏吗?这款游戏出了续作,炸弹的威力大大加强了。
游戏的地图是一个二维平面。JYY 的阵地位于 x 轴下方,而所有的敌人目前都位于 x 轴上方。
在 JYY 的阵地中有建有 T 个激光塔和 S 个发射源。其中第 i 个防御塔 Ti 的坐标为 (txi,tyi),第 i 个发射源 Si 的坐标为 (sxi,syi)。
地图上有 D 个敌人,第 i 个敌人 Di 的坐标为 (dxi,dyi)。
两座激光塔可以相互连接形成能量墙。发射源朝向敌人发出的能量如果穿过了能量墙,可以得到巨大的加强而变为「超级射线」并瞬间消灭敌人。
JYY 想知道他有多少种可以可以发出超级射线的攻击方案。
具体来说,一个可以发出超级射线的攻击方案为一个由四个点组成的集合:{Ti,Tj,Sk,Dl},满足 1≤i<j≤T,1≤k≤S,1≤l≤D,并且线段 TiTj 和线段 SkDl 相交。
游戏设定保证在这 T+D+S 个点中,不存在重点也不存在三点共线。
输入格式
第一行包含一个正整数 D;
接下来 D 行,每行包含两个整数 dxi,dyi,表示一个敌人的坐标;
第 D+1 行包含一个整数 S;
接下来 S 行,每行包含两个整数 sxi,syi,表示一个发射源的坐标;
第 D+S+2 行包含一个整数 T;
接下来 T 行,每行包含两个整数 txi,tyi,表示一个激光塔的坐标。
输出格式
输出一行一个整数,可以发出超级射线的攻击方案个数。
输入输出样例
输入#1
3 1 12 10 30 30 10 1 10 -10 4 2 -11 9 -1 11 -1 15 -14
输出#1
7
说明/提示
对于 20% 的数据,满足 D,S,T≤30;
对于 50% 的数据,满足 D,S,T≤150;
对于 100% 的数据,满足 1≤D,S,T≤800,dyi>0,syi,tyi<0,所有坐标绝对值不超过 109。