Usted debe escribir un programa o función que, dada una Npor Nrejilla cuadrada igualmente espaciados y un sólido salidas círculo inscrito o devuelve el número de cuadrados de rejilla que se solapan parcial o totalmente por el círculo sólido.

Las superposiciones de tamaño 0 (es decir, cuando el círculo solo toca una línea) no se cuentan. (Estas superposiciones ocurren, por ejemplo, en N = 10).

Ejemplo

N = 8 (64 squares), Slices = 60

Entrada

• Un entero N > 0. (La cuadrícula tendrá N * Ncuadrados).

Salida

• Un número entero, el número de rodajas de círculo sólido.

Ejemplos

(pares de entrada-salida)

Inputs:  1 2 3  4  5  6  7  8  9 10  11  12  13  14  15
Outputs: 1 4 9 16 25 36 45 60 77 88 109 132 149 172 201

Este es el código de golf, por lo que gana la entrada más corta.

Pyth, 27 26

-*QQ*4lfgsm^d2T*QQ^%2_UtQ2

Pruébelo en línea: Pyth Compiler / Executor

Yo uso una 2Nx2Ncuadrícula y cuento 2x2cuadrados superpuestos . Eso es un poco más corto, ya que conozco el radio N.

Y en realidad no cuento los cuadrados superpuestos. Cuento los cuadrados no superpuestos del segundo cuadrante, multiplico el número por 4 y restamos el resultado N*N.

Explicación de la solución 27:

-*QQ*4lfgsm^-Qd2T*QQ^t%2UQ2   implicit: Q = input()
                     t%2UQ    generates the list [2, 4, 6, ..., Q]
                    ^     2   Cartesian product: [(2, 2), (2, 4), ..., (Q, Q)]
                              These are the coordinates of the right-down corners
                              of the 2x2 squares in the 2nd quadrant. 
       f                      Filter the coordinates T, for which:
        gsm^-Qd2T*QQ             dist-to-center >= Q
                                 more detailed: 
          m     T                   map each coordinate d of T to:
           ^-Qd2                       (Q - d)^2
         s                          add these values
        g        *QQ                 ... >= Q*Q
    *4l                       take the length and multiply by 4
-*QQ                          Q*Q - ...

Explicación de la solución 26:

Me di cuenta de que uso las coordenadas solo una vez e inmediatamente resta las coordenadas Q. ¿Por qué no simplemente generar los valores Q - coordsdirectamente?

Esto sucede en %2_UtQ. Solo un char más grande que en la solución anterior y ahorra 2 caracteres, porque no tengo que restar -Q.

Pitón 2, 72

lambda n:sum(n>abs(z%-~n*2-n+(z/-~n*2-n)*1j)for z in range(~n*~n))+n+n-1

Sin golf:

def f(n):
    s=0
    for x in range(n+1):
        for y in range(n+1):
            s+=(x-n/2)**2+(y-n/2)**2<(n/2)**2
    return s+n+n-1

La cuadrícula apunta a un (n+1)*(n+1)cuadrado. Una celda se superpone al círculo si su punto de cuadrícula más cercano al centro está dentro del círculo. Entonces, podemos contar los puntos de la cuadrícula, excepto que esto pierde 2*n+1puntos de la cuadrícula en los ejes (tanto para pares como para impares n), por lo que corregimos eso manualmente.

El código guarda caracteres al usar distancias complejas para calcular la distancia al centro y un colapso de bucle para iterar sobre un índice único.

CJam, 36 35 34 27 bytes

Resultó ser el mismo algoritmo que el de xnor, pero me pregunto si hay uno mejor.

rd:R,_m*{{2*R(-_g-}/mhR<},,

Explicación del código :

rd:R                                "Read the input as double and store it in R";
    ,_                              "Get 0 to input - 1 array and take its copy";
      m*                            "Get Cartesian products";
                                    "Now we have coordinates of top left point of each";
                                    "of the square in the N by N grid";
        {               },,         "Filter the squares which are overlapped by the";
                                    "circle and count the number";
         {        }/                "Iterate over the x and y coordinate of the top left";
                                    "point of the square and unwrap them";
          2*                        "Scale the points to reflect a 2N grid square";
            R(-                     "Reduce radius - 1 to get center of the square";
               _g-                  "Here we are reducing or increasing the coordinate";
                                    "by 1 in order to get the coordinates of the vertex";
                                    "of the square closer to the center of the grid";
                    mhR<            "Get the distance of the point from center and check";
                                    "if its less than the radius of the circle";

ACTUALIZACIÓN : ¡Usando el truco 2N de Jakube junto con algunas otras técnicas para ahorrar 7 bytes!

Pruébalo en línea aquí

Pyth  44  36

JcQ2L^-+b<bJJ2sm+>*JJ+y/dQy%dQqQ1*QQ

Tratando de limpiarlo un poco en caso de que pudiera reducir algunos bytes.

Explicación

                           Q = eval(input())    (implicit)
JcQ2                       calculate half of Q and store in J
L                          define function y(b) that returns
 ^-+b<bJJ2                 (b - J + (1 if b < J else 0)) ^ 2
s                          output sum of
 m                 *QQ      map d over integers 0..(Q*Q-1)
  +
   >*JJ                      J*J is greater than
       +y/dQy%dQ              sum of y(d / Q) and y(d % Q)
                qQ1          or Q is 1; see below

Tengo que verificar explícitamente n = 1 , ya que mi algoritmo solo verifica la esquina del cuadrado más cercano al centro (y ninguno está cubierto n = 1).

Octava (74) (66) (64)

Aquí la versión de octava. Básicamente, encontrar todos los vértices dentro del círculo y luego encontrar todos los cuadrados con uno o más vértices válidos por convolución. 64 bytes:

x=ndgrid(-1:2/input(''):1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

66 bytes:

x=meshgrid(-1:2/input(''):1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

74 bytes:

n=input('');x=ones(n+1,1)*(-1:2/n:1);sum(conv2(x.^2+x'.^2<1,ones(2))(:)>0)

R - 64

function(n)sum(rowSums(expand.grid(i<-0:n-n/2,i)^2)<n^2/4)+2*n-1