[AtCoder] ABC 191 D – Circle Lattice Points

2021年2月25日

問題

方針

整数 \( a \) を用いて、直線 \( x = a \) と円の交点を \( (a, b_1) , (a, b_2) \ (b_1 \leq b_2)\) とします。このときの格子点の数は、

\[ \lfloor b_2 \rfloor – \lceil b_1 \rceil + 1\]

となるので、\( a \) を全探索します。\( a \) の範囲は、\(\lceil a – R \rceil \leq a \leq \lfloor a + R \rfloor \) です。交点は、\( (x – X)^2 + (y – Y)^2 = R^2 \) より、\( y = Y \pm \sqrt{R^2 – (a – X)^2} \)を利用すれば良いです。

この問題の一番の問題点は精度誤差なので、PythonのDecimalを使って解きます。

コード

Python

from decimal import Decimal
X, Y, R = map(Decimal, input().split())

sx = Decimal.__ceil__(X - R)
ex = Decimal.__floor__(X + R)
ans = 0
for i in range(sx, ex + 1):
    sy = Decimal.__ceil__(Y - Decimal.sqrt(R * R - (i - X) * (i - X)))
    ey = Decimal.__floor__(Y + Decimal.sqrt(R * R - (i - X) * (i - X)))
    ans += ey - sy + 1
print(ans)

参考