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 :