【bzoj1822】 [JSOI2010]Frozen Nova 冷冻波

2014年12月15日2,2186

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

题解

二分时间,计算几何判断每个巫师可以攻击到哪些精灵,网络流判定

 

  • Lesphere2016年3月20日 下午8:41 回复

    题上说不能有任何公共点,好像巫妖与精灵的连线与树木所在圆相切是可以的?
    还有您的点到线段距离为何这样写,题目数据有问题?

    #1  
    • Lesphere2016年3月20日 下午9:20 回复

      我又打错网络流,但数据确实够水的

      #11
    • HugeG2016年3月20日 下午9:51 回复

      %%%lesphere

      #11
    • hzwer2016年4月11日 下午8:50 回复
      admin

      这个写法有什么问题么。。。

      #11
      • Lesphere2016年4月13日 下午12:56 回复

        若点P与线段AB,成以∠APB为钝角的三角形,dot>0,不就有问题

        #12
        • Loading2016年4月14日 上午8:08 回复

          不能以∠APB是否为钝角为依据 应该是判断∠PAB 或∠PBA是否为钝角

          #13