Divida el primer cuadrante (incluido el eje x positivo, el eje y positivo y el origen) en cuadrículas de 1x1, con cada cuadrícula etiquetada por las coordenadas de su esquina inferior izquierda, como se muestra a continuación:

Tenga en cuenta que cada cuadrícula contiene sus límites y sus vértices. Usando símbolos matemáticos, la cuadrícula etiquetada (m, n) representaría el cuadrado {(x,y) | m ≤ x ≤ m+1, n ≤ y ≤ n+1}.

Dada una línea recta en forma de ax+by+c=0con enteros a, by c, y una cuadrícula representada por (m,n), indique si la línea pasa a través de la cuadrícula, es decir, si algún punto de la cuadrícula dada está en la línea.

a  b  c m n output
1  1  0 0 0 true
1  1  0 1 1 false
1  1  0 0 2 false
1  1 -3 0 1 true
1  1 -3 0 0 false
2 -1  0 1 1 true
2 -1  0 1 0 false
2 -1  0 0 2 true
2 -1  0 0 1 true
2 -1  0 1 2 true
2  0 -1 0 0 true
2  0 -1 0 1 true
2  0 -1 0 2 true
2  0 -1 1 0 false
2  0 -1 1 1 false
0  2 -1 0 0 true
0  2 -1 1 0 true
0  2 -1 2 0 true
0  2 -1 0 1 false
0  2 -1 1 1 false
1  0 -1 0 0 true
1  0 -1 0 1 true
1  0 -1 0 2 true
1  0 -1 1 0 true
1  0 -1 1 1 true

Por favor, sugiera más casos de prueba en los comentarios.

Este es el código de golf . La respuesta más corta en bytes gana. Se aplican lagunas estándar .

Python 3, 84 66 bytes

Primer golf, primer fracaso (tal vez).

Gracias a Rod por reducir 18 bytes utilizando una función en lugar de una entrada directa.

def f(a,b,c,m,n):f=-(a*m+c)/b;g=f-a/b;print(min(f,g)<=n<=max(f,g))

Pruébalo en línea!

Explicación:

Básicamente calculamos el valor de la función de línea para m y m + 1, si n está entre los valores, entonces la lista debe pasar por él en algún momento. Sería mucho mejor si el lenguaje tuviera una forma más simple de ingresar múltiples enteros.

Jalea , 10 bytes

ż‘{Œpæ.ṠE¬

Pruébalo en línea!

Antecedentes

Al igual que otras respuestas antes de la mía, esto se basa en el hecho de que una línea recta divide el plano en dos semiplanos. El rectángulo está contenido en uno de estos semiplanos (sin intersección con la línea) o intersecta ambos semiplanos (y, por lo tanto, la línea que los separa).

Cómo funciona

ż‘{Œpæ.ṠE¬  Main link. Left argument: [m, n]. Right argument: [a, b, c]

 ‘{         Increment left; yield [m+1, n+1].
ż           Zipwith; yield [[m, m+1], [n, n+1]].
   Œp       Cartesian product; yield [[m, n], [m, n+1], [m+1, n], [m+1, n+1]].
     æ.     Take the dot products with [a, b, c], mapping each [x, y] to ax+by+c.
       Ṡ    Take the signs.
        E   Test the signs for equality.
         ¬  Logical NOT.

Python 2 , 59 bytes

lambda a,b,c,m,n:min(0,a,b,a+b)<=-a*m-b*n-c<=max(0,a,b,a+b)

Pruébalo en línea!

Podemos decir de qué lado de la línea está un punto por el signo de a*x+b*y+c. La línea pasa a través del cuadrado (contando tocar) a menos que los cuatro vértices (m,n),(m,n+1),(m+1,n),(m+1,n+1)estén estrictamente en el mismo lado de la línea. Podemos conectar estos valores en un extracto de la constante a*m+b*n+cque aparece en los cuatro:

a*m+b*n+c
a*m+b*n+c+a
a*m+b*n+c+b
a*m+b*n+c+a+b

Entonces, la línea pasa a través del cuadrado a menos que estos cuatro valores sean todos positivos o todos negativos. Por lo tanto, es suficiente que su mínimo sea <=0y el máximo sea >=0.

min(a*m+b*n+c,a*m+b*n+c+a,a*m+b*n+c+b,a*m+b*n+c+a+b)<=0<=max(a*m+b*n+c,a*m+b*n+c+a,a*m+b*n+c+b,a*m+b*n+c+a+b)

Restar lo común a*m+b*n+cde cada parte da el código.

Un enfoque un poco más largo es verificar si el conjunto de signos (+, 0, -) tiene una longitud de al menos 2.

Python 2 , 62 bytes

lambda a,b,c,m,n:len({cmp(a*m+b*n+c,-d)for d in(0,a,b,a+b)})>1

Pruébalo en línea!

Mathematica, 60 55 bytes

Solve[m#+n#2==-#3&&#4<=m<=#4+1&&#5<=n<=#5+1,{m,n}]!={}&

-5 bytes gracias a @MartinEnder

formulario de entrada

[a, b, c, m, n]

Lote, 66 bytes

@cmd/cset/a"q=%1*%4+%2*%5+%3,((-(q+%1)*(q+%2)&-q*(q+%1+%2))>>31)+1

Explicación: consideramos los valores tomados por la ecuación en las cuatro esquinas de la celda. Si la línea no cruza la celda, los cuatro valores tienen el mismo signo, pero si cruza la celda, al menos un valor será cero o el signo opuesto. La comparación se simplifica multiplicando pares de esquinas opuestas, luego, si ambos valores son positivos, la línea no intersecta la celda. Un poco de giro de bits convierte las multiplicaciones en un resultado general.

Mathematica, 50 bytes

-4<Tr@Sign[Tuples@{{#,#+1},{#2,#2+1}}.{##4}+#3]<4&

Pruébalo en línea!

Toma m, n, c, a, bcomo entrada en ese orden.

Explicación: Tuples@{{#,#+1},{#2,#2+1}}hace una lista de las coordenadas de las cuatro esquinas del cuadrado, luego toma el producto de punto con .{##4}(lo que significa {#4, #5}) y agrega +#3cálculos ax + by + cpara x,ycada esquina. Si la línea pasa por el punto, esto es cero; si la línea está más lejos del origen, es negativa; y si la línea está más cerca del origen, es positiva, por lo tanto, verificamos la Signs de estos cuatro valores. La línea pasa fuera del cuadrado si y solo si los cuatro valores son 1 o los cuatro son -1, por lo que verificamos que su suma esté estrictamente entre -4 y 4.

(Esta respuesta está vagamente inspirada por mi respuesta a esta pregunta ).

Python 2, 147 110 bytes

def f(a,b,c,m,n):
 if b:d=sorted((-a*x-c)/float(b)for x in(m,m+1));return d[0]-1<=n<=d[1]
 return m<=-c/a<=m+1

¡Y muchas gracias a Leaky Nun!

TIO

Python , 54 bytes

lambda a,b,c,m,n:abs(2*(a*m+b*n+c)+a+b)<=abs(a)+abs(b)

Pruébalo en línea!

(Gracias a xnor por el script de prueba).

Cómo funciona

La línea pasa por m + 1/2 + x , n + 1/2 + y si y solo si

a ⋅ ( m + 1/2 + x ) + b ⋅ ( n + 1/2 + y ) + c = 0
⇔ 2⋅ ( a ⋅ m + b ⋅ n + c ) + a + b = −2⋅ a ⋅ x - 2⋅ b ⋅ y .

Esto es posible para algunos | x |, | y | ≤ 1/2 si y solo si | 2⋅ ( a ⋅ m + b ⋅ n + c ) + a + b | ≤ | a | + | b |.

Java (OpenJDK 8) , 71 bytes

(a,b,c,x,y)->(0<a?0:a)+(0<b?0:b)<=(x=-a*x-b*y-c)&x<=(0>a?0:a)+(0>b?0:b)

Pruébalo en línea!

Puerto de la solución Python de xnor.

Solución original, utilizando la intersección de forma / línea de Java incorporada (108 bytes)

(a,b,c,x,y)->b==0?x<=-c/a&-c/a<=x+1:new java.awt.Rectangle(x,y,1,1).intersectsLine(x,c=(c+a*x)/-b,x+1,c-a/b)

Pruébalo en línea!

Créditos

• -8 bytes gracias a ceilingcat