Napisz program lub funkcję, która podając całkowity promień r zwraca liczbę jednostek kwadratów, przez które przechodzi promień r wyśrodkowany na początku. Jeśli okrąg przechodzi dokładnie przez punkt na siatce, który nie jest liczony jako przejście przez sąsiednie kwadraty jednostek.

Oto ilustracja dla r = 5 :

^{Ilustracja Kival Ngaokrajang, znaleziona w OEIS}

Przykłady:

0 → 0
1 → 4
4 → 28
5 → 28
49 → 388
50 → 380
325 → 2540
5524 → 44180
5525 → 44020

Python 2 , 54 bajty

f=lambda r,x=0:r-x and-~((r*r-x*x)**.5%1>0)*4+f(r,x+1)

Wypróbuj online!

Mniej golfa (55 bajtów) ( TIO )

lambda r:8*r-4*sum((r*r-x*x)**.5%1==0for x in range(r))

Ocenia to wynik jako 8*r, a następnie koryguje przecięcia wierzchołków. Wynik jest taki 8*r-g(r*r), że g(x)liczy się liczba sposobów pisania xjako suma dwóch kwadratów (oprócz g(0)=0).

Jeśli okrąg nigdy nie przechodzi przez żadne wierzchołki, liczba dotkniętych komórek byłaby równa liczbie skrzyżowanych krawędzi. Okrąg przechodzi przez 2*rpionowe linie siatki i 2*rpoziome linie siatki, mijając je w obu kierunkach, w sumie 8*r.

Ale każde przejście na wierzchołku liczy się jako dwa skrzyżowania krawędzi, jednocześnie wchodząc tylko do jednej nowej komórki. Tak więc kompensujemy odejmując liczbę skrzyżowań wierzchołków. Obejmuje to punkty na osiach, jak (r,0)również tróje pitagorejskie, jak (4,3)na r=5.

Liczymy na jednym kwadrancie punkty (x,y)z x>=0i y>0z x*x+y*y==n, a następnie pomnożyć przez 4. Robimy to poprzez zliczanie LICZBA sqrt(r*r-x*x)które są cały numer do xw przedziale [0,r).

Mathematica, 48 bajtów

4Count[Range@#~Tuples~2,l_/;Norm[l-1]<#<Norm@l]&

Patrzy na pierwszy kwadrant i liczy liczbę komórek siatki, dla których dane wejściowe mieszczą się między normami lewego dolnego i prawego górnego rogu komórki (oczywiście mnożąc wynik przez 4).

Python 2 , 72 bajty

lambda n:sum(0<n*n-x*x-y*y<2*(x-~y)for x in range(n)for y in range(n))*4

Wypróbuj online!

Galaretka , 21 13 12 11 bajtów

R²ạ²Æ²SạḤ×4

Wypróbuj online!

Jak to działa

R²ạ²Æ²SạḤ×4  Main link. Argument: r

R            Range; yield [1, 2, ..., r].
 ²           Square; yield [1², 2², ..., r²].
   ²         Square; yield r².
  ạ          Absolute difference; yield [r²-1², r²-2², ..., r²-r²].
    Ʋ       Test if each of the differences is a perfect square.
      S      Sum, counting the number of perfect squares and thus the integer
             solutions of the equation x² + y² = r² with x > 0 and y ≥ 0.
        Ḥ    Un-halve; yield 2r.
       ạ     Subtract the result to the left from the result to the right.
         ×4  Multiply by 4.

Perl 6, 61 bajtów

->\r{4*grep {my &n={[+] $_»²};n(1 X+$_)>r²>.&n},(^r X ^r)}

Jak to działa

->\r{                                                    } # Lambda (accepts the radius).
                                                (^r X ^r)  # Pairs from (0,0) to (r-1,r-1),
                                                           #   representing the bottom-left
                                                           #   corners of all squares in
                                                           #   the top-right quadrant.
       grep {                                 }            # Filter the ones matching:
             my &n={[+] $_»²};                             #   Lambda to calculate the norm.
                              n(1 X+$_)>r²                 #   Top-right corner is outside,
                                          >.&n             #   and bottom-left is inside.
     4*                                                    # Return length of list times 4.

AWK, 90 bajtów

{z=$1*$1
for(x=$1;x>=0;x--)for(y=0;y<=$1;y++){d=z-x*x-y*y
if(d>0&&d<2*(x+y)+2)c++}$0=4*c}1

Stosowanie:

awk '{z=$1*$1
    for(x=$1;x>=0;x--)for(y=0;y<=$1;y++){d=z-x*x-y*y
    if(d>0&&d<2*(x+y)+2)c++}$0=4*c}1' <<< 5525

Wystarczy przeszukać kwadrant 1, aby znaleźć wszystkie pola, które przecinają okrąg. Symetria pozwala na pomnożenie przez 4. Może pochodzić z -$1 to $1, ale to zajmie więcej bajtów i będzie mniej wydajne. Oczywiście nie jest to najbardziej efektywny czasowo algorytm, ale uruchomienie skrzynki 5525 na moim komputerze zajmuje tylko około 16 sekund.

Haskell, 74 bajty

f n=sum[4|x<-[0..n],y<-[0..n],(1+n-x)^2+(1+n-y)^2>n^2,(n-x)^2+(n-y)^2<n^2]

Całkiem prosto, policz liczbę kwadratów między (0,0) a (n, n), gdzie lewy dolny jest wewnątrz koła, a prawy górny jest poza okręgiem, a następnie pomnóż przez 4.

Pyth , 29 bajtów

Lsm*ddb*4lf}*QQrhyTym+1dT^UQ2

Spróbuj!

Wyjaśnienie

Lsm*ddb*4lf}*QQrhyTym+1dT^UQ2  # implicit input: Q
Lsm*ddb                        # define norm function
 s                             # sum
  m   b                        #     map each coordinate to
   *dd                         #                            its square
                         ^UQ2  # cartesian square of [0, 1, ..., Q - 1]
                               #     -> list of coordinates of all relevant grid points
          f                    # filter the list of coordinates T where:
           }*QQ                # square of Q is in
               r               #     the range [
                hyT            #         1 + norm(T),
                               #                  ^ coordinate of lower left corner
                   ym+1dT      #         norm(map({add 1}, T))
                               #              ^^^^^^^^^^^^^^^ coordinate of upper right corner
                               #     ) <- half-open range
         l                     # size of the filtered list
                               #     -> number of passed-through squares in the first quadrant
       *4                      # multiply by 4
                               # implicit print

Partia, 147 bajtów

@set/an=0,r=%1*%1
@for /l %%i in (0,1,%1)do @for /l %%j in (0,1,%1)do @set/a"i=%%i,j=%%j,a=i*i+j*j-r,i+=1,j+=1,a&=r-i*i-j*j,n-=a>>31<<2
@echo %n%

Nieco inspirowane odpowiedziami AWK i Haskell.

Narzędzia Bash + Unix, 127 bajtów

c()(d=$[(n/r+$1)**2+(n%r+$1)**2-r*r];((d))&&echo -n $[d<0])
r=$1
bc<<<`for((n=0;n<r*r;n++));{ c 0;c 1;echo;}|egrep -c 01\|10`*4

Wypróbuj online!

Wystarczy przejrzeć wszystkie punkty w pierwszej ćwiartce, policzyć je i pomnożyć przez 4. Może być bardzo wolny, ale działa.

JavaScript (ES7), 76 bajtów

n=>4*(G=k=>k<n?Math.ceil((n**2-k++**2)**0.5)-(0|(n**2-k**2)**0.5)+G(k):0)(0)