AtCoder-ABC191 D - Circle Lattice Points【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

2完だったAtCoder Beginner Contest191の復習です。
この記事ではD問題を記事にしていきます。
atcoder.jp

AtCoder Beginner Contest191 D - Circle Lattice Points

問題文

2 次元平面上に中心 (X,Y) 、半径 R の円があります。
この円の内部または周上にある格子点 (x,y 座標がともに整数である点) の個数を求めてください。

制約

・|X|≤10^5
・|Y|≤10^5
・0

解答例

import math

xf, yf, rf = map(float,input().split())
x = round(xf * 10000)
y = round(yf * 10000)
r = round(rf * 10000)

start = (x - r) // 10000 # 格子点xの最小値
end = (x + r) // 10000 # 格子点xの最大値

ans = 0
for i in range(start,end + 1):
    tmp = pow(r, 2) - pow(x - i*10000, 2)
    if tmp >= 0:
        l = math.isqrt(tmp)
        ymax = int((y + l) // 10000) # x = i のときの最大のyの格子点
        ymin = int((y - l -1) // 10000) # x = i のときの最小のyの格子点
        ans += ymax - ymin # x=i におけるyの格子点の数
else:
    print(ans)

解説

問題文の通り、二次元平面上の点(X,Y)を中心として、半径Rの円があります。
この円の内部や周上に格子点が何個あるか答える問題です。

与えられるX,Y,Rは小数点以下4桁の値になることがあり、誤差が問題になりますので10^4をかけて整数にしました。

格子点を数える方法はx =c(整数)となる線を考えます。
円と交わるx = cは、円の半径がRなので 2R 本引くことができます。
Rがわかっているので三平方の定理を用いれば、x = c 上の y の格子点の最大値と最小値を求めることができます。
よってyの最大値から最小値を引けばx = c 上の格子点の数となります。

円に交わるすべてのx = cで同様の計算を行うことで、求める格子点の数がわかります。
（円に外接する正方形の範囲で、すべての格子点が該当するか調べる全探索ではTLEとなってしまいます。）

コード内のstart変数はループを始める値、end変数はループ終了の値を計算しています。
この範囲内でループさせて、円に交わるすべての x = c で格子点の数を足し合わせました。
ループを抜けた後に足し合わせた数を格納したans変数を出力すればACでした。

誤差に配慮して与えられた入力を整数にして計算すること、単純な全探索では間に合わないなどトラップがたくさんある問題でした。
加えてfloatを消したつもりでも小数が出力されたりと実装も大変でした。

コンテストでこの問題を解けたらうれしかったなあ、って思います。
本当に解くことができるように今後も学習を続けていきたいです！

ABC191の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com