首页 > 其他分享 >洛谷 P4048更新题面

洛谷 P4048更新题面

时间:2023-03-02 19:23:49浏览次数:44  
标签:施法 10 洛谷 题面 样例 小精灵 坐标 100 P4048

[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

标签:施法,10,洛谷,题面,样例,小精灵,坐标,100,P4048
From: https://www.cnblogs.com/yuhang-ren/p/17173050.html

相关文章

  • 洛谷P4051 [JSOI2007]字符加密 题解 后缀数组sa的应用
    题目链接:https://www.luogu.com.cn/problem/P4051题目大意:给定一个长度为\(n\)的字符串\(s\),每次将\(s\)的首字符取出放到末尾……这样能得到\(n\)个字符串。将......
  • 位运算-洛谷P1469 找筷子
    位运算的符号:与(&) and当两个数在二进制下对应位数上均为 11 时,得到的结果为 11.或(|) or当两个数在二进制下对应位数上有一个为 11 时,得到的结果为 11.......
  • [洛谷]P5401 [CTS2019] 珍珠 题解
    [洛谷]P5401[CTS2019]珍珠题解题意概述有\(D\)种珍珠,每种有无限颗,现在等概率的从\(D\)种珍珠中抽\(n\)次珍珠,每次抽\(1\)个珍珠,记第\(i\)种珍珠最后一共抽......
  • 【LGR-(-17)】洛谷入门赛 #8 个人赛后总结
    【LGR-(-17)】洛谷入门赛#8个人赛后总结前言这是本蒟蒻的第一篇博客,也是对第一次参加洛谷比赛的总结,如果有错误请指出。引子本蒟蒻第一次看到比赛时就迫不及待的报了......
  • 洛谷P1149
    [洛谷P1149]([P1149NOIP2008提高组]火柴棒等式-洛谷|计算机科学教育新生态(luogu.com.cn))publicclassP1149{ publicstaticvoidmain(String[]args){ S......
  • P4048 [JSOI2010]冷冻波 题解
    首先很好想到我们应该预处理出来每一个巫妖王能攻击到的精灵。那么这就是一个几何题。对于每一组精灵与巫妖王,设巫妖王坐标为\((x_1,y_1)\),精灵坐标为\((x_2,y_2)\)。......
  • 洛谷P8471 [Aya Round 1 F] 琪露诺的选择题
    原题传送门题目描述有2⋅n道选择题,每题有A和B两个选项。正确答案可以表示为一个长度为2⋅n的字符串。现在你要构造出一份作答(长度同样为2⋅n的字符串),其中恰好......
  • AcWing356/洛谷P4180 次小生成树
    涉及知识点:最小生成树,倍增题意题目链接(洛谷)题目链接(AcWing)题目写的很清楚,给定一张N个点M条边的无向图,求无向图的严格次小生成树。设最小生成树的边权之和为sum,严格次......
  • 「题解」洛谷 P5829 【模板】失配树
    crashednb/se不过它解释为什么跳\(k\bmodd+d\)确实有点迷,不懂为什么直接跳\(k\bmodd\)会挂可以手摸一下峰峰峰的hack,从25开始跳。简单做法就是建出失配树然后......
  • 洛谷P2341/USACO03FALL 受欢迎的牛
    题意分析题目链接喜欢是单向的,喜欢有传递性……Emmm这听起来好像……对了,就是连通性问题!我们不妨将奶牛之间的喜欢关系表示为一条条单向边,怎么求明星奶牛的数量呢?这里......