Солярій для Грибів (Складна)#4361

Солярій для Грибів (Складна) (Розбір)

Розділимо множину точок з цілими координатами на п'ять частин, як показано на рисунку: одна точка знаходиться в центрі, а решта чотири частини симетричні між собою і покривають чотири чверті кола. Якщо кількість точок, що лежать в одній з чвертей, дорівнює $r es$ , то загальна кількість точок в колі буде $4 \cdot r es + 1$ 4 \cdot res + 1.

Обчислимо значення $r es$ . Нехай радіус кола дорівнює $r$ . Переберемо значення $y$ від $0$ до $r$ . Тоді на прямій $y = k (0 \leq k \leq r)$ y = k~(0 \le k \le r) усередині кола опиниться $⌊ r^{2} - k^{2} ⌋$ \left\lfloor {\sqrt{r^2 - k^2}}\right\rfloor точок з цілими координатами. Загальна кількість таких точок на усіх рівнях $y$ і буде значенням $r es$ :

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

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

Позначимо через $f (r)$ загальну кількість цілих точок усередині кола радіуса $r$ . Тоді:

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

Функція f монотонно зростає. Завдання полягає в тому, щоб знайти мінімальне значення $r$ , для якого виконується рівність $f (r) = n$ f(r) = n. Радіус лампи $r$ будемо шукати за допомогою бінарного пошуку.

Реалізація алгоритму

Функція count повертає кількість точок з цілими координатами, розташованих усередині кола радіуса $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++

Основна частина програми. Читаємо вхідне значення $n$ .

scanf("%lld",&n);

Радіус кола, який покриває щонайменше $n$ точок, шукаємо за допомогою бінарного пошуку. Спочатку припускаємо, що шуканий радіус знаходиться в діапазоні $[l; r] = [0; 1000000]$ [l; r] = [0; 1000000].

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

Якщо кількість точок в колі радіуса $m$ менша $n$ , збільшуємо ліву границю інтервалу до $m + 1$ m + 1 — радіуса $m$ недостатньо для покриття $n$ точок. В іншому випадку зменшуємо праву границю.

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

Виводимо відповідь.

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