Hi, I was trying to solve atcoder's ABC191 problem D
Problem statement - Given X, Y, R that define a circle centered at (X, Y) with radius R, find the number of grid points whose x- and y-coords are integers, that lie within or on the circle.
Constraints are: |X|, |Y|, R < 1e5 (X, Y, and R can be floating point values upto 4 decimal places)
Approach used -
The equation of a circle is (x-a)^2 + (y-b)^2 = R^2 for a circle centered at (a, b)
So I figure the qn wants me to solve the integral solutions to (x-a)^2 + (y-b)^2 <= R^2
I isolate (y-b)^2 and iterate over all candidate values of x from [-a-R-1, a+R+1] and compute the lower and upper bound of y and add them all up and output them.
For some reason this fails — I observed this is also pretty different from the editorial approach. Is there something fundamentally wrong with my idea/code?
a, b, r = [float(i) for i in input().split()] ''' (x-a)^2 + (y-b)^2 <= r^2 => (y-b)^2 <= r^2 - (x-a)^2 k = r^2 - (x-a)^2 y <= sqrt(K)+b y >= b-sqrt(K) ''' ans = 0 from math import floor, ceil for x in range(-int(a)-int(r)-2, int(a)+int(r)+3): k = r*r - (x-a)**2 if k<0: continue ans += max(0, 1 + floor(k**0.5 + b) - ceil(b-(k**0.5))) print(ans)