[JSOI2010]Frozen Nova 冷冻波

[JSOI2010]Frozen Nova 冷冻波

Time Limit:10000MS  Memory Limit:65536K
Total Submit:77 Accepted:22
Case Time Limit:1000MS

Description

WJJ喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能Frozen Nova每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。
当巫妖和小精灵之间的直线距离不超过R,且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的连线与任何树木都没有公共点)的话,巫 妖就可以瞬间杀灭一个小精灵。
在森林里有N个巫妖,每个巫妖释放Frozen Nova之后,都需要等待一段时间,才能再次施放。不同的巫妖有不同的等待时间和施法范围,但相同的是,每次施放都可以杀死一个小精灵。
现在巫妖的头目想知道,若从0时刻开始计算,至少需要花费多少时间,可以杀死所有的小精灵?

Input

输入文件第一行包含三个整数N、M、K(N,M,K<=200),分别代表巫妖的数量、小精灵的数量和树木的数量。
接下来N行,每行包含四个整数x, y, r, t,分别代表了每个巫妖的坐标、攻击范围和施法间隔(单位为秒)。
再接下来M行,每行两个整数x, y,分别代表了每个小精灵的坐标。
再接下来K行,每行三个整数x, y, r,分别代表了每个树木的坐标。
输入数据中所有坐标范围绝对值不超过10000,半径和施法间隔不超过20000。

Output

输出一行,为消灭所有小精灵的最短时间(以秒计算)。如果永远无法消灭所有的小精灵,则输出-1。

Sample Input

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

Sample Output

5

Source

JSOI2010第二轮Contest1

JSOI2010第二轮Contest161.187.179.132:8080/JudgeOnline/showproblem
由于文章过长就不贴题目了囧。。变态题。。JSOI2010 Contest1中最难的了囧。写的半死囧还WA几次。
题意太恶心了啊,就是目光与树相交也算看到囧。。
我的代码慢的跟鬼一样囧。。
很显然要二分答案然后判断,判断的话网络流随便建个图就可以了。。
关键是计算几何部分,太恶心了囧。。
关键是一条线与不与一个圆相交,首先算出圆心到这个线的距离,然后跟半径比较一下,
点到线段的距离怎么求呢?就是这个点跟线段两端点组成三角形的面积除以底边长,面积用叉积算就可以了。。
Code:百度太垃圾了,长点的代码就发不了囧。。
只好放ideone上了囧。。
www.ideone.com/erv1eoAI

 

  

2 thoughts on “[JSOI2010]Frozen Nova 冷冻波

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>