ZOJ 3379. Master Spark

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3956
http://watashi.ws/blog/touhou-monthly/touhou-monthly-solutions/marisa/

Brief description :

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

Analyse :

扫描线,对每一个点,得到一个入事件 (t-d, 1)和出事件 t+d, -1)。(将点旋转到 y=ax^2 上,然后通过解三角形得到二次方程,再解二次方程得到。)
注意的扫描线区域是个环形,需要破环为链。
(注意相同坐标时,应该优先处理出事件,不过好像没有这种数据。)

http://vjudge.net/vjudge/problem/viewSource.action?id=2782195

External link :