Écrivez un programme ou une fonction qui, étant donné un rayon entier r, renvoie le nombre de carrés unitaires que le cercle de rayon r centré à l'origine traverse. Si le cercle passe exactement par un point de la grille qui ne compte pas comme passant par les carrés d'unité adjacents.

Voici une illustration pour r = 5 :

^{Illustration de Kival Ngaokrajang, trouvée sur OEIS}

Exemples:

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

Python 2 , 54 octets

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

Essayez-le en ligne!

Moins golfé (55 octets) ( TIO )

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

Cela estime la sortie comme 8*r, puis corrige les croisements de sommets. Le résultat est 8*r-g(r*r), où g(x)compte le nombre de façons d'écrire xcomme une somme de deux carrés (sauf g(0)=0).

Si le cercle ne traversait aucun sommet, le nombre de cellules touchées serait égal au nombre d'arêtes croisées. Le cercle passe par 2*rdes quadrillages verticaux et des quadrillages 2*rhorizontaux, passant chacun dans les deux directions, pour un total de 8*r.

Mais, chaque croisement à un sommet compte comme deux croisements de bord tout en n'entrant que dans une nouvelle cellule. Donc, nous compensons en soustrayant le nombre de croisements de sommets. Cela inclut les points sur les axes comme (r,0)ainsi que les triplets pythagoriciens comme (4,3)pour r=5.

Nous comptons pour un seul quadrant les points (x,y)avec x>=0et y>0avec x*x+y*y==n, puis multiplions par 4. Nous faisons cela en comptant les sqrt(r*r-x*x)nombres qui sont des nombres entiers pour xdans l'intervalle [0,r).

Mathematica, 48 octets

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

Examine le premier quadrant et compte le nombre de cellules de la grille pour lesquelles l'entrée se situe entre les normes des coins inférieur gauche et supérieur droit de la cellule (en multipliant le résultat par 4, bien sûr).

Python 2 , 72 octets

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

Essayez-le en ligne!

Gelée , 21 13 12 11 octets

R²ạ²Æ²SạḤ×4

Essayez-le en ligne!

Comment ça marche

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 octets

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

Comment ça marche

->\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 octets

{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

Usage:

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

Une simple recherche dans le quadrant 1 pour trouver toutes les cases qui coupent le cercle. La symétrie permet la multiplication par 4. Pourrait aller de -$1 to $1, mais cela prendrait plus d'octets et serait moins efficace. Évidemment, ce n'est pas l'algorithme le plus efficace en temps, mais il ne faut que 16 secondes environ pour exécuter le boîtier 5525 sur ma machine.

Haskell, 74 octets

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]

Assez simple, comptez le nombre de carrés entre (0,0) et (n, n) où le coin inférieur gauche est à l'intérieur du cercle et le coin supérieur droit est à l'extérieur du cercle, puis multipliez par 4.

Pyth , 29 octets

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

Essayez!

Explication

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

Lot, 147 octets

@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%

Assez inspiré par les réponses AWK et Haskell.

Utilitaires Bash + Unix, 127 octets

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

Essayez-le en ligne!

Parcourez tous les points du premier quadrant, comptez-les et multipliez par 4. Cela peut être très lent, mais cela fonctionne.

JavaScript (ES7), 76 octets

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)