円 格子点 個数 python 備忘録

ABC191D
atcoder.jp

Pythonのdecimalを使う
(C++とかでやると地獄を見ることになります。)

from decimal import Decimal
from math import ceil,floor
def solve():
  X,Y,R=map(Decimal,input().split())
  start=ceil(X-R)
  end=floor(X+R)
  num=0
  for i in range(start,end+1):
    top=floor(Y+Decimal(R**2-(X-i)**2).sqrt())
    bottom=ceil(Y-Decimal(R**2-(X-i)**2).sqrt())
    num+=top-bottom+1
  return num

pypyだとTLEする。
これはdecimalが遅いらしい(？)。

floorは負の無限大に、ceilは正の無限大への丸めであることに注意する。