列表

详情

NC20228. [JSOI2016]炸弹攻击 2

描述

还记得那款题为“炸弹攻击”的塔防游戏吗？这款游戏出了续作，炸弹的威力大大加强了。
游戏的地图是一个 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 行，每行包含两个整数(dxi , dyi)(dyi > 0)，表示一个敌人的坐标。
第 D+1 行包含一个整数 S。
接下来 S 行，每行包含两个整数(sxi , syi) (syi < 0)，表示一个发射源的坐标。
第 D+S+2 行包含一个整数 T。
接下来 T 行，每行包含两个整数(txi , tyi) (tyi < 0)，表示一个激光塔的坐标。

输出描述

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

示例1

输入: 

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

输出: 

7

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

上一题

© 2024 nowcoder.com