Edit

【pythonでABC191を解説】D - Circle Lattice Points

問題概要

問題ページ

D - Circle Lattice Points
D - Circle Lattice Points

問題ページへ移動する

問題文

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

制約

  • \(|X| \le 10^5\)
  • \(|Y| \le 10^5\)
  • \(0 \lt R \le 10^5\)
  • \(X, Y, R\) は高々小数第 \(4\) 位まで与えられる

問題の考察

ACコード

import sys
import math
import decimal


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    x, y, r = list(map(decimal.Decimal, input().rstrip('\n').split()))
    cnt = 0
    for i in range(math.ceil(x - r), math.floor(x + r) + 1):
        n = decimal.Decimal(i) - x
        s = (r * r - n * n).sqrt()
        cnt += math.floor(y + s) - math.ceil(y - s) + 1
    print(cnt)


if __name__ == '__main__':
    solve()

-Edit
-