読者です 読者をやめる 読者になる 読者になる

AOJ 0090 Overlaps of Seals

f:id:peroon:20170507143500j:plain

問題はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0090

私の解答はこちら http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2300900#1

2次元ベクトルをクラス定義する代わりに複素数(complex)を使ってみたら平均やnormalizeが楽だった。解法は、まず円と円の交点を列挙する。次に各交点が円に含まれる回数をカウントする。円に含まれるかの判定は、交点と円の中心の距離が1以下かどうかなのだが、誤差の関係で1以下で判定したら通らず、1.01以下で判定すると通った。ロジックは合ってるけど誤差でWrong Answerになっているときは、原因を突き止めにくい。下のように判定を甘くして誤差を無視できるようにした。

if abs(intersection - p) <= 1.01:
    cnt += 1