marisa. Master Spark

marisa. Master Spark

ZOJ3379. Master Spark (极限火花)

downloadsource code (ZOJ3379.cpp) [解析几何, 排序+扫描线]

神偷摸你傻的招牌SC——Master Spark在东方系列多部作品都作为自机bomb和敌机SC存在着,虽然其实Master Spark是盗自风间幽香的。DA☆ZE则是摸你傻的著名口癖。原本打算找一个场面宏大的Master Spark作为配图,不过最后从wikia选的这个也颇具喜感的。作为幻想乡最大后宫团的拥有者,不愧为人生的赢家。魔理沙は大切なものを盗んでいきました!(魔理沙偷走了重要的東西),又是miko的电波+鬼畜……上过アニサマ2008……不过好像是黑历史……

  • 奇妙な魔法使い/普通の黒魔術師/普通の魔法使い/霧雨魔理沙(きりさめ まりさ)

假设摸你傻的魔炮是一个角度可选,射程无限,伤害区域是二次项系数为a,顶点在原点的抛物线。二维平面内有一些妖精,问摸你傻的一次魔炮最多能伤害多少妖精。

算法是经典的排序+扫描线。首先对于每个在(x, y)的妖精,可以求出但魔炮的极角选择在那个区间内时,能够击中该点。显然这个区间是[alpha - delta, alpha + delta]形式的,其中alpha就是极角atan2(y, x),而delta可以通过解z^2+(az^2)^2=x^2+y^2; tan(delta)=az^2/z求得。于是问题就是找一个角度beta,使得最多的区间包含这个角度。先对所有区间排序,然后从-PI到PI,对关键极角扫描,维护能够攻击到的妖精数,最大值就是答案。要注意处理头和尾的情况,比如挂在这个9个妖精的case(红色取得最优解):

case9

这题把每个区间作为pair<double, double>排序后用priority_queue<double>不是最简单的(我的就是这样)。更好的方法是直接把一个区间变成两个pair<double, bool>排序,写起来非常简单(t__nt是这么写的)。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

5 Responses to “marisa. Master Spark”
  1. newfarking says:

    我随机函数生成了好多数据,都和标程对到了,可还是wa了

  2. hzhua says:

    4 1
    1 1
    1 -1
    -1 -1
    -1 1

    这个数据为什么是3 daze啊
    不是2么

  3.  
Leave a Reply