编程介的小学生 2017-09-02 13:08 采纳率: 20.3%
浏览 952
已采纳

Nova

Problem Description
The Lich is a powerful hero that he can kill a wisp with his skill Frost Nova. The Burning Legion wants to conquer the forest so they sent some liches to kill all the wisps. A lich can kill a wisp once he could see the wisp and the wisp in his attack range. So the lich can attack a wisp when the distance between them is less than or equal to specific R and no trees are on the segment between the lich and wisp. Each lich has a cool down time that once he used Frost Nova he has to wait a few seconds for the next attack. Different liches may have different attack range and cool down time. The Lich King is the leader of the Burning Legion and he wants to arrange the attack order so the liches can wipe out all the wisps as soon as possible.

Input
The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers N, M, K, indicating the number of lich, the number of wisps and the number of trees. The next N lines, each line consists of four integers x, y, r, t indicating the coordinate of that a lich, the radius of the attack range that lich’s Frost Nova can reach and the value of cool down time. The next M lines, each line consists of two integers x, y indicating the coordinate of each wisp. The last K lines, each line consists of three integers x, y, r, indicating the coordinate and radius of a tree. A lich cannot attack a wisp if the segment between them has a common point with the tree. The lich, wisp and trees will not overlap with each other.

Output
Output the minimum time lich need to kill all the wisps on a single line, or -1 if lich cannot kill all the wisps.

Constrains
0 < T <= 20
0 <= N, M, K <= 200
-10000 <= x, y <= 10000
0 <= r, t <= 10002

Sample Input
1
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

Sample Output
5

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-09-16 16:26
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 我下载图形界面重启完就变成这样了,打字也打不了,动也动不了,该怎么解决(操作系统-centos)
  • ¥15 VBA中在窗体中遍历所有checkbox控件,提取出被选中的checkbox的caption值
  • ¥15 在Ubuntu上有什么命令,或者是系统文件能告诉我链接nvme ssd的pcie槽位是不是支持热插拔功能?
  • ¥15 ansys license许可证问题
  • ¥20 QQ号和密码都能正常登录微信 QQ号和密码登录微信显示密码错误
  • ¥15 qiankun主应用注册子应用提示跨域
  • ¥15 单片机RTOS Kernel与应用分离开发,Kernel如何调起应用?
  • ¥15 快手小店商家版APP怎么第三方APP跳转到指定用户聊天界面
  • ¥15 为什么AVL fire软件仿真时的步长改变了,仿真结果也会改变
  • ¥100 如何帮我写一个java小游戏