Göbələklər üçün Solyaris (Çətin)#4361

Göbələklər üçün Solyaris (Çətin) (Həll təhlili)

Nöqtələrin tam ədədi koordinatlarla olan çoxluğunu şəkildə göstərildiyi kimi beş hissəyə ayıraq: bir nöqtə mərkəzdədir, qalan dörd hissə isə öz aralarında simmetridir və dairənin dörd rübünü əhatə edir. Bir rübdə yerləşən nöqtələrin sayı $r es$ -ə bərabərdirsə, onda dairədəki ümumi nöqtələrin sayı $4 \cdot r es + 1$ 4 \cdot res + 1-ə bərabər olacaq.

Gəlin $r es$ dəyərini hesablayaq. Qoy dairənin radiusu $r$ -yə bərabər olsun. $y$ dəyərlərini $0$ -dan $r$ -ə qədər yoxlayaq. Beləliklə, $y = k (0 \leq k \leq r)$ y = k~(0 \le k \le r) doğrusunda dairənin içərisində tam ədədi koordinatlara malik $⌊ r^{2} - k^{2} ⌋$ \left\lfloor{\sqrt{r^2 - k^2}}\right\rfloor nöqtə olacaq. Bütün $y$ səviyyələrində belə nöqtələrin ümumi sayı $r es$ -in dəyəri olacaq:

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

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

$f (r)$ ilə radiusu $r$ olan dairənin daxilindəki tam ədədi nöqtələrin ümumi sayını göstərək. O zaman:

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 funksiyası monoton olaraq artır. Problem $f (r) = n$ f(r) = n bərabərliyinin təmin edildiyi minimal $r$ dəyərini tapmaqdan ibarətdir. Lampanın radiusunu isə binar axtarış üsulu ilə axtaracağıq.

Alqoritmin reallaşdırılması

count funksiyası radiusu $r$ olan dairənin daxilindəki tam ədədi koordinata malik nöqtələrin sayını qaytarı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++

Proqramın əsas hissəsi. Girişdən $n$ dəyərini oxuyuruq.

scanf("%lld",\u0026n);

Ən azı $n$ nöqtəni əhatə edən dairənin radiusunu binar axtarış üsulu ilə axtarırıq. Əvvəlcə tələb olunan radiusu $[l; r] = [0; 1000000]$ [l; r] = [0; 1000000] diapazonunda olduğunu qəbul edirik.

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

Əgər radiusu $m$ olan dairədəki nöqtələrin sayı $n$ -dən azdırsa, biz $m + 1$ m + 1-ə qədər olan intervalın sol sərhədini artırırıq — radiusu $m$ olan dairə $n$ nöqtəni əhatə etmək üçün kifayət deyil. Əks halda, sağ sərhədi azaldırıq.

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

Cavabı çap edirik.

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