Description:
N枚(N<=100)の円盤を積み上げた時上からほんの少しでも見える円盤は何枚あるか?
各円盤の座標と半径は小数点12桁の精度で与えられ、全ての点の座標は、-10<=x,y<=10を満たしている。
点が5*10^-13だけずれても、見える円盤の数が変わることは無い。
Answer:
円周がどの円との境界線になっているかを全て調べればよい。
各円について、他の円との交点を求め、円周がどのように分割されるかを調べる。
分割された円周の、ちょっと内側の点、ちょっと外側の点に対して、実際にどの円とぶつかるかテスト。
計算量は、曲線の分割数がO(n^2)、ぶつかるかテストがO(n)のO(n^3)
Source: