사각형과 원이 겹치는 영역의 좌표의 개수는 O(N)에 구할 수 있을까

21676번: Газон (acmicpc.net) 왼쪽 아래 (x1,y1), 오른쪽 위 (x2,y2)로 주어지는 사각형과 중심 (x3,y3), 반지름 r로 주어지는 원이 서로 겹치는 영역의 정수 점 (x,y)의 개수를 구하는 문제 정말 단순하게 생각하면 사각형 안의 모든 정수 점 (x,y)에 대하여 원의 방정식 내부 (x-x3)**2 + (y-y3)**2  def check(x,y): v = (x-x3)**2 + (y-y3)**2 if v   하지만 x1,x2,y1,y2,x3,y3의 범위가 -10만~10만이라 $O(N^{2})$은 시간초과가 날수밖에 없다 하지만... 이것말고 방법이 있나? x를 정했으면 그거에 대해 y는 모든 범위를 돌아봐야할텐데..? 방법은 원의 방정식은 (x-x3)..