#PQJ120x6221. QOJ 120_6221

    ID: 2573 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2016枚举

QOJ 120_6221

第二轮第二试 炸弹攻击2 炸弹攻击2 【故事背景】 还记得那款题为“炸弹攻击”的塔防游戏吗?这款游戏出了续作,炸弹的威 力大大加强了。 【问题描述】 游戏的地图是一个2 维平面。JYY 的阵地位于x 轴下方,而所有的敌人目前 都位于x 轴上方。 在JYY 的阵地中有建有T 个激光塔和S 个发射源。其中第i 个防御塔𝑇"的坐 标为(𝑡𝑥", 𝑡𝑦"),第i 个发射源𝑆"的坐标为(𝑠𝑥", 𝑠𝑦")。 地图上有D 个敌人,第i 个敌人𝐷"的坐标为(𝑑𝑥", 𝑑𝑦")。 两座激光塔可以相互连接形成能量墙。发射源朝向敌人发出的能量如果穿过 了能量墙,可以得到巨大的加强而变为“超级射线”并瞬间消灭敌人。 JYY 想知道他有多少种可以可以发出超级射线的攻击方案。 具体来说,一个可以发出超级射线的攻击方案为一个由四个点组成的集合: {𝑇", 𝑇>, 𝑆L, 𝐷M},满足1 ≤𝑖< 𝑗< 𝑇, 1 ≤𝑘≤𝑆, 1 ≤𝑙≤𝐷 并且线段𝑇"𝑇>和线段𝑆L𝐷M 相交。 游戏设定保证在这𝑇+ 𝐷+ 𝑆个点中,不存在重点也不存在三点共线。 【输入格式】 从文件attack2.in 中读入数据。 第一行包含一个正整数D。 接下来D 行,每行包含两个整数𝑑𝑥", 𝑑𝑦" (𝑑𝑦" > 0),表示一个敌人的坐标。 第D+1 行包含一个整数S。 接下来S 行,每行包含两个整数𝑠𝑥", 𝑠𝑦" (𝑠𝑦" < 0),表示一个发射源的坐标。 第D+S+2 行包含一个整数T。 接下来T 行,每行包含两个整数𝑡𝑥", 𝑡𝑦" (𝑡𝑦" < 0),表示一个激光塔的坐标。 【输出格式】 输出到文件attack2.out 中。 输出一行一个整数,可以发出超级射线的攻击方案个数。 【输入样例】 3 1 12 10 30

第二轮第二试 炸弹攻击2 30 10 1 10 -10 4 2 -11 9 -1 11 -1 15 -14 【输出样例】 7 【数据规模】 对于20%的数据满足 𝐷, 𝑆, 𝑇≤30。 对于50%的数据满足 𝐷, 𝑆, 𝑇≤150。 对于100%的数据满足1 ≤𝐷, 𝑆, 𝑇≤800,所有坐标绝对值不超过105。