La siguiente imagen muestra el problema:

Escriba una función que, dado un número entero como el radio del círculo, calcule el número de puntos de la red dentro del círculo centrado (incluido el límite).

La imagen muestra:

f[1] = 5  (blue points)
f[2] = 13 (blue + red points)  

Otros valores para su comprobación / depuración:

f[3]    = 29
f[10]   = 317
f[1000] = 3,141,549
f[2000] = 12,566,345  

Debe tener un rendimiento razonable. Digamos menos de un minuto para f [1000].

El código más corto gana. Se aplican las reglas habituales de Code-Golf.

Publique el cálculo y el momento de f [1001] como ejemplo.

J, 21 19 18

+/@,@(>:|@j./~@i:)

Construye complejos de -x-xj a x + xj y toma magnitud.

Editar: con >:

Edición 2: Con gancho y monádico ~. Corre algunas veces más lento por alguna razón, pero aún así 10 segundos para f (1000).

J, 27 21

3 :'+/,y>:%:+/~*:i:y'

Muy brutal: calcula sqrt (x² + y²) sobre el rango [-n, n] y cuenta los elementos ≤n . Todavía tiempos muy aceptables para 1000.

Editar : i:yes bastante más corto que y-i.>:+:y. Gracias Jesse Millikan !

Ruby 1.9, 62 58 54 caracteres

f=->r{1+4*eval((0..r).map{|i|"%d"%(r*r-i*i)**0.5}*?+)}

Ejemplo:

f[1001]
=> 3147833

t=Time.now;f[1001];Time.now-t
=> 0.003361411

Python 55 Chars

f=lambda n:1+4*sum(int((n*n-i*i)**.5)for i in range(n))

Haskell, 41 bytes

f n=1+4*sum[floor$sqrt$n*n-x*x|x<-[0..n]]

Cuenta puntos en el cuadrante x>=0, y>0, multiplica por 4, suma 1 para el punto central.

Haskell, 44 bytes

f n|w<-[-n..n]=sum[1|x<-w,y<-w,x*x+y*y<=n*n]

JavaScript (ES6), 80 bytes (no compite porque ES6 es demasiado nuevo)

n=>(a=[...Array(n+n+1)].map(_=>i--,i=n)).map(x=>a.map(y=>r+=x*x+y*y<=n*n),r=0)|r

Versión alternativa, también 80 bytes:

n=>[...Array(n+n+1)].map((_,x,a)=>a.map((_,y)=>r+=x*x+(y-=n)*y<=n*n,x-=n),r=0)|r

Versión ES7, también 80 bytes:

n=>[...Array(n+n+1)].map((_,x,a)=>a.map((_,y)=>r+=(x-n)**2+(y-n)**2<=n*n),r=0)|r

Python 2, 48 bytes

f=lambda n,i=0:i>n or(n*n-i*i)**.5//1*4+f(n,i+1)

Como la solución de fR0DDY , pero recursiva, y devuelve un flotante. Devolver un int es de 51 bytes:

f=lambda n,i=0:i>n or 4*int((n*n-i*i)**.5)+f(n,i+1)

C (gcc) , 60 bytes

r,a;f(x){for(a=r=x*x;a--;)r-=hypot(a%x+1,a/x)>x;x=4*r+1;}

Pruébalo en línea!

Recorre el primer cuadrante, multiplica el resultado por 4 y agrega uno. Ligeramente menos golfizado

r,a;
f(x){
  for(a=r=x*x;a--;)
    r-=hypot(a%x+1,a/x)>x;
  x=4*r+1;
}

APL (Dyalog Extended) , 14 bytes

{≢⍸⍵≥|⌾⍀⍨⍵…-⍵}

Pruébalo en línea!

A pesar de carecer del i:(incluido rango de -n a n) incorporado de J, APL Extended tiene una sintaxis más corta en otras áreas.

{≢⍸⍵≥|⌾⍀⍨⍵…-⍵}            Monadic function taking an argument n.
           ⍵…-⍵             n, n-1, ..., -n
      ⌾⍀                   Make a table of complex numbers
                            (equivalent to ∘.{⍺+1J×⍵} in Dyalog APL)
         ⍨                  with both real and imaginary parts from that list.
      |                       Take their magnitudes.
    ⍵≥                        1 where a magnitude are is at most n, and 0 elsewhere.
 ⍸                           Get all indices of truthy values.
≢                            Find the length of the resulting list.

Japt -x , 12 bytes

òUn)ï Ëx²§U²

Pruébalo en línea!

Explicación:

òUn)            #Get the range [-input ... input]
    ï           #Get each pair of numbers in that range
      Ë         #For each pair:
       x        # Get the sum...
        ²       # Of the squares
         §      # Check if that sum is less than or equal to...
          U²    # The input squared
                #Output the number of pairs that passed the check

PHP, 85 83 bytes

El código:

function f($n){for($x=$n;$x;$c+=$x,$y++)for(;$n*$n<$x*$x+$y*$y;$x--);return$c*4+1;}

Su resultado (ver https://3v4l.org/bC0cY para varias versiones de PHP):

f(1001)=3147833
time=0.000236 seconds.

El código no golfista:

/**
 * Count all the points having x > 0, y >= 0 (a quarter of the circle)
 * then multiply by 4 and add the origin.
 *
 * Walk the lattice points in zig-zag starting at ($n,0) towards (0,$n), in the
 * neighbourhood of the circle. While outside the circle, go left.
 * Go one line up and repeat until $x == 0.
 * This way it checks about 2*$n points (i.e. its complexity is linear, O(n))
 *
 * @param int $n
 * @return int
 */
function countLatticePoints2($n)
{
    $count = 0;
    // Start on the topmost right point of the circle ($n,0), go towards the topmost point (0,$n)
    // Stop when reach it (but don't count it)
    for ($y = 0, $x = $n; $x > 0; $y ++) {
        // While outside the circle, go left;
        for (; $n * $n < $x * $x + $y * $y; $x --) {
            // Nothing here
        }
        // ($x,$y) is the rightmost lattice point on row $y that is inside the circle
        // There are exactly $x lattice points on the row $y that have x > 0
        $count += $x;
    }
    // Four quarters plus the center
    return 4 * $count + 1;
}

Una implementación ingenua que verifica los $n*($n+1)puntos (y funciona 1000 más lento, pero aún calcula f(1001)en menos de 0.5 segundos) y el conjunto de pruebas (usando los datos de muestra proporcionados en la pregunta) se puede encontrar en github .

Clojure / ClojureScript, 85 caracteres

#(apply + 1(for[m[(inc %)]x(range 1 m)y(range m):when(<=(+(* x x)(* y y))(* % %))]4))

Bruto fuerza el primer cuadrante, incluido el eje y pero no el eje x. Genera un 4 para cada punto, luego los agrega junto con 1 para el origen. Se ejecuta en menos de 2 segundos para una entrada de 1000.

Abusa muchísimo de fordefinir una variable y guardar algunos caracteres. Hacer lo mismo para crear un alias rangeno guarda ningún carácter (y lo hace correr significativamente más lento), y parece poco probable que vaya a guardar algo haciendo una función cuadrada.

Pyke, 14 bytes, no competidor

QFXQX-_,B)s}}h

Pruébalo aquí!

Mathematica, 35 caracteres

f[n_]:=Sum[SquaresR[2,k],{k,0,n^2}]

Levantado de https://oeis.org/A000328

https://reference.wolfram.com/language/ref/SquaresR.html

SquaresR[2,k]es el número de formas de representar k como la suma de dos cuadrados, que es igual al número de puntos de la red en un círculo de radio k ^ 2. Suma de k = 0 a k = n ^ 2 para encontrar todos los puntos en o dentro de un círculo de radio n.

Tcl, 111 bytes

lassign {1001 0 -1} r R x
while {[incr x]<$r} {set R [expr {$R+floor(sqrt($r*$r-$x*$x))}]}
puts [expr {4*$R+1}]

Bucle x discreto simple sobre el cuadrante I, contando el mayor y utilizando el teorema de Pitágoras en cada paso. El resultado es 4 veces la suma más uno (para el punto central).

El tamaño del programa depende del valor de r . Reemplace {1001 0 -1}con "$argv 0 -1"y puede ejecutarlo con cualquier valor de argumento de línea de comando para r .

Calcula f (1001) → 3147833.0en aproximadamente 1030 microsegundos, procesador AMD Sempron 130 2.6GHz de 64 bits, Windows 7.

_{Obviamente, cuanto mayor es el radio, más cercana es la aproximación a PI: f (10000001) se ejecuta en aproximadamente 30 segundos produciendo un valor de 15 dígitos, que es aproximadamente la precisión de un doble IEEE.}

Stax , 11 bytes

ä÷²M╨⌐■╝^₧░

Ejecutar y depurarlo