Solarium for mushrooms (Hard)#4361

Solarium for mushrooms (Hard) (Editorial)

Let us divide the set of points with integer coordinates into five parts, as shown in the figure: one point lies at the center, and the remaining four parts are symmetric and cover the four quadrants of the circle. If the number of points lying in one quadrant is $r es$ , then the total number of points inside the circle will be $4 \cdot r es + 1$ 4 \cdot res + 1.

Let's compute the value of $r es$ . Let the radius of the circle be $r$ . We iterate over the values of $y$ from $0$ to $r$ . Then, on the line $y = k (0 \leq k \leq r)$ y = k~(0 \le k \le r), there will be $⌊ r^{2} - k^{2} ⌋$ \left\lfloor {\sqrt{r^2 - k^2}}\right\rfloor points with integer coordinates lying inside the circle. The total number of such points across all y levels gives us the value of $r es$ :

k = 0 \sum r ⌊ r^{2} - k^{2} ⌋

\sum_{k=0}^r \left\lfloor {\sqrt{r^2 - k^2}}\right\rfloor

Let $f (r)$ denote the total number of integer-coordinate points inside a circle of radius $r$ . Then:

f (r) = 4 \cdot k = 0 \sum r ⌊ r^{2} - k^{2} ⌋ + 1

f(r) = 4 \cdot \sum_{k=0}^r \left\lfloor {\sqrt{r^2 - k^2}} \right\rfloor + 1

The function f is monotonically increasing. The task is to find the smallest value of $r$ such that the equation $f (r) = n$ f(r) = n holds. We'll use binary search to find the required radius $r$ of the lamp.

Algorithm implementation

The function count returns the number of points with integer coordinates that lie inside a circle of radius $r$ .

long long count(long long r)
{
  long long res = 0;
  double r2 = r * r;
  for (long long y = 0; y <= r; y++)
    res += (long long)sqrt(r2 - y*y);
  return 4 * res + 1;
}

C++

The main part of the program. Read the input value $n$ .

scanf("%lld",&n);

Search for the radius of the circle that covers at least n points using binary search. Initially, we assume that the desired radius lies within the range $[l; r] = [0; 1000000]$ [l; r] = [0; 1000000].

l = 0; r = 1000000;
while (l < r)
{
   m = (l + r ) / 2;

If the number of points inside a circle of radius $m$ is less than $n$ , increase the left boundary of the interval to $m + 1$ m + 1, the radius $m$ is not sufficient to cover $n$ points. Otherwise, decrease the right boundary.

   if (count (m) < n) l = m + 1; else r = m;
}

Print the answer.

printf("%d\n",l);