洛谷 P4048更新题面
2024-10-20 20:43:58
[JSOI2010]冷冻波
题目描述
WJJ 喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能 Frozen Nova 每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。
当巫妖和小精灵之间的直线距离不超过 \(R\),且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的连线与任何树木都没有公共点)的话,巫妖就可以瞬间杀灭一个小精灵。
在森林里有 \(N\) 个巫妖,每个巫妖释放 Frozen Nova 之后,都需要等待一段时间,才能再次施放。不同的巫妖有不同的等待时间和施法范围,但相同的是,每次施放都可以杀死一个小精灵。
现在巫妖的头目想知道,若从 \(0\) 时刻开始计算,至少需要花费多少时间,可以杀死所有的小精灵?
输入格式
输入文件第一行包含三个整数 \(N、M、K(N,M,K \le 200)\),分别代表巫妖的数量、小精灵的数量和树木的数量。
接下来N行,每行包含四个整数 \(x, y, r, t\),分别代表了每个巫妖的坐标、攻击范围和施法间隔(单位为秒)。
再接下来M行,每行两个整数 \(x, y\),分别代表了每个小精灵的坐标。
再接下来K行,每行三个整数 \(x, y, r\),分别代表了每个树木的坐标。
输入数据中所有坐标范围绝对值不超过 \(10^{4}\),半径和施法间隔不超过\(2 \times 10^{4}\)。
输出格式
输出一行,为消灭所有小精灵的最短时间(以秒计算)。如果永远无法消灭所有的小精灵,则输出 \(-1\)。
样例 #1
样例输入 #1
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10
样例输出 #1
5
最新文章
- 你真的会玩SQL吗?你所不知道的 数据聚合
- Blender 之 Splash 代码分析
- 用unity4.3发布WINDOWS STORE APP应用的方法
- 致第一次安装RIME的你
- C语言-12-日期和时间处理标准库详细解析及示例
- iOS Auto Layout
- 【转】System.Data.OracleClient requires Oracle client software version 8.1.7 or greater
- 用css属性画出一棵圣诞树
- MyBatis笔记----MyBatis查询表全部的两种方法:XML与注解
- Web API中的Help Page
- Linux拉你入门
- Effective前端1---chapter 2 用CSS画一个三角形
- 聊聊Zookeeper应用场景、架构设计、选主机制
- Python操作rabbitmq消息队列持久化
- 隔行变色&;&;鼠标移入变色
- django额外参数的传递和url命名
- 对layoutInflater的理解
- 【51nod】1773 A国的贸易
- How To Setup Apache Hadoop On CentOS
- C# Web Service简单使用