There are two circles, given by 2nd coordinates and radius - (x1, y1, r1) , (x2, y2, r2) .

It is necessary to find the number of points with integer coordinates that are simultaneously in two circles. All values ​​of the module do not exceed 10 6 .

UPD: Here is my attempt:

 x1, y1, r1 = map(int, input().split(' ')) x2, y2, r2 = map(int, input().split(' ')) size_x_min = min([x1-r1, x2-r2]) size_x_max = max([x1+r1, x2+r2]) size_y_min = min([y1-r1, y2-r2]) size_y_max = max([y1+r1, y2+r2]) r1 = r1**2 r2 = r2**2 count = 0 for y in range(size_y_min, size_y_max): for x in range(size_x_min, size_x_max): if (x1 - x)**2 + (y1 - y)**2 <= r1 and (x2 - x)**2 + (y2 - y)**2 <= r2: count += 1 print(count)

But the code runs too slowly.

Example:
env 1 - (0, 0, 5)
env 2 - (2, 2, 3)
Points (answer) - 26

  • related: - jfs
  • does not relate directly to the question: an interesting video about the connection of the number of points on the coordinate grid located inside the circle, prime numbers, complex numbers and π youtu.be/NaL_Cb42WyY - jfs
  • Why did you bring the Olympiad task here? Olympiad problems need to be solved by yourself. I hope someone will inform the organizers of the Olympiad about this issue. - VladD

2 answers 2

But the code is too slow.

Your algorithm is quadratic in radius. Using the smaller of the two radii will not change this. In the worst case, one circle in another lies, therefore the number of points in the intersection is equal to the number of points in the smaller circle. The number of points lying on the coordinate grid inside the circle is proportional to the area of ​​the circle, that is, ~ r 2 . Therefore, any method in which points one by one are considered to be quadratic, that is, it leads to ~ 10 12 operations in this case (slowly).

You can use a linear algorithm to improve efficiency for large radii. At the end of the answer by reference, a detailed explanation of why a quadratic algorithm is much worse than a linear one (for large radii).

To obtain a linear algorithm, you can bypass only one coordinate (for example, vertically along y ), and calculate the number of points (horizontal) at the intersection immediately, determining the intersection of the intervals bounded by given circles:

 from math import ceil, floor def count_lattice_points_intersection(a, b): count = 0 for y in range(ay - ar, ay + ar + 1): # scan from bottom to top if by - br <= y <= by + br: # intersection is possible # find intersection boundaries for given y ax1, ax2 = x_coordinates_intesect(a, y) bx1, bx2 = x_coordinates_intesect(b, y) if min(ax2, bx2) >= max(ax1, bx1): # intersect count += floor(min(ax2, bx2)) - ceil(max(ax1, bx1)) + 1 return count def x_coordinates_intesect(c, y): """Get x-coordinates of intersection of circle *c* and horizontal line *y*.""" # solve quadratic equation # (x - cx)**2 + (y - cy)**2 == cr**2 assert cr**2 >= (y - cy)**2 D = (cr**2 - (y - cy)**2)**.5 return cx - D, cx + D

The boundaries of the intervals are solved by solving a quadratic equation for a circle:

 (x - cx)**2 + (y - cy)**2 == cr**2

Example :

lattice points of two circles intersection

 from collections import namedtuple Circle = namedtuple('Circle', 'x, y, r') print(count_lattice_points_intersection(Circle(0, 0, 5), Circle(2, 2, 3))) # -> 26

26 points of the coordinate lattice are inside the given circles.

    You iterate through the points of a square containing both circles. This is the right decision, but there are too many such points. As an initial square, it suffices to take a square in which a smaller circle is inscribed (more precisely, one should speak about circles, and not circles).

    • one
      this may change the constant, but the algorithm will still remain quadratic in radius (~ 10 ^ 12 operations). There is a linear solution - jfs
    • @jfs You are absolutely right, and your answer, of course, is much more effective (the code did not look, but the description of the algorithm is absolutely correct). I wonder if there is an algorithm faster O (r)? - andy.37
    • An even simpler problem of the number of points of the coordinate lattice within one circle does not have a closed formula ( Gauss Circle Problem ) - the error (difference from the area of ​​the circle) is not precisely known (estimate r ** (1/2 + eps)). O (r) solution . - jfs