Need help in geometry problem

Revision en2, by venti, 2021-08-04 21:39:51

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 on some tests — I observed this is also pretty different from the editorial approach. Is there something fundamentally wrong with my idea/code?

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)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English venti 2021-08-04 21:39:51 14 Tiny change: 'his fails &mdash; ' -> 'his fails on some tests &mdash; '
en1 English venti 2021-08-04 21:37:55 1335 Initial revision (published)