Führt diese Linie durch dieses Quadrat?

19

Teilen Sie den ersten Quadranten (einschließlich der positiven x-Achse, der positiven y-Achse und des Ursprungs) in 1x1-Gitter, wobei jedes Gitter durch die Koordinaten seiner linken unteren Ecke gekennzeichnet ist, wie unten gezeigt:

Beachten Sie, dass jedes Raster seine Grenzen und Scheitelpunkte enthält. Mit mathematischen Symbolen würde das mit (m, n) bezeichnete Gitter das Quadrat darstellen {(x,y) | m ≤ x ≤ m+1, n ≤ y ≤ n+1}.


Bei einer geraden Linie in der Form von ax+by+c=0mit ganzen Zahlen a, b, und c, und ein Gitter , dargestellt durch den (m,n)Ausgang ob die Zeile des Gitter durchläuft, das heißt , ob jeder Punkt in dem gegebenen Raster auf der Linie ist.


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

Bitte schlagen Sie in den Kommentaren weitere Testfälle vor.


Das ist . Kürzeste Antwort in Bytes gewinnt. Es gelten Standardlücken .

Undichte Nonne
quelle
1
Natürlich sollten wir davon ausgehen können, dass nicht sowohl a als auch b 0 sind, denn wenn c Null ist, kann es unendlich viele Zeilen geben, und wenn c nicht Null ist, kann es überhaupt keine Zeile geben.
Erik der Outgolfer
Kann ich Eingaben als zwei oder mehr Arrays erhalten, z. B. [a, b, c](die Linie) und [m, n](das Quadrat)?
Erik der Outgolfer
@EriktheOutgolfer Ich bin überrascht, dass das nicht in Meta ist.
Undichte Nonne
Related
Kein Baum
Stark verwandt .
Olivier Grégoire

Antworten:

5

Python 3, 84 66 Bytes

Erstes Golfen, zuerst scheitern (vielleicht).

Vielen Dank an Rod für das Abschneiden von 18 Bytes mithilfe einer Funktion anstelle der direkten Eingabe.

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

Probieren Sie es online!

Erläuterung:

Grundsätzlich berechnen wir den Wert der Linienfunktion für m und m + 1. Wenn n zwischen den Werten liegt, muss die Liste ihn irgendwann durchlaufen. Wäre viel besser, wenn die Sprache auf einfachere Weise mehrere Ganzzahlen eingeben könnte.

verletzt
quelle
2
Willkommen bei PPCG!
Betseg
1
Muss dies nicht mit n + 1 und m + 1 verglichen werden?
Neil
3
Division durch Null wenn bist 0.
Olivier Grégoire
Außerdem besteht es nicht mehrere Testfälle, die von Leaky Nun hervorgehoben wurden.
Olivier Grégoire
5

Gelee , 10 Bytes

ż‘{Œpæ.ṠE¬

Probieren Sie es online!

Hintergrund

Wie andere Antworten vor mir beruht dies auf der Tatsache, dass eine gerade Linie die Ebene in zwei Halbebenen unterteilt. Das Rechteck ist entweder in einer dieser Halbebenen enthalten (kein Schnittpunkt mit der Linie) oder schneidet beide Halbebenen (und damit die Linie, die sie trennt).

Wie es funktioniert

ż‘{Œ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.
Dennis
quelle
4

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)

Probieren Sie es online!

Wir können anhand des Zeichens von erkennen, auf welcher Seite der Linie sich ein Punkt befindet a*x+b*y+c. Die Linie verläuft durch das Quadrat (Berührungen werden gezählt), es sei denn, alle vier Scheitelpunkte (m,n),(m,n+1),(m+1,n),(m+1,n+1)befinden sich genau auf derselben Seite der Linie. Wir können diese Werte in einem Extrakt aus der Konstante einfügen, die a*m+b*n+cin allen vier vorkommt:

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

Die Linie verläuft also durch das Quadrat, es sei denn, diese vier Werte sind alle positiv oder alle negativ. Es genügt also, dass ihr Minimum <=0und Maximum ist >=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)

Subtrahiert man das Gemeinsame a*m+b*n+cvon jedem Teil, erhält man den Code.

Ein etwas längerer Ansatz besteht darin, zu überprüfen, ob die Menge der Zeichen (+, 0, -) eine Länge von mindestens 2 hat.

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

Probieren Sie es online!

xnor
quelle
3

Mathematica, 60 55 Bytes

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

-5 Bytes Danke an @MartinEnder

Eingabeformular

[a, b, c, m, n]

J42161217
quelle
2
Ah, ich wünschte, jede Sprache hätte eine SolveFunktion ...
Erik the Outgolfer
3

Batch, 66 Bytes

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

Erklärung: Wir betrachten die von der Gleichung an den vier Ecken der Zelle genommenen Werte. Wenn die Linie die Zelle nicht schneidet, haben alle vier Werte das gleiche Vorzeichen. Wenn sie jedoch die Zelle schneidet, ist mindestens ein Wert Null oder das entgegengesetzte Vorzeichen. Der Vergleich wird vereinfacht, indem Paare von gegenüberliegenden Ecken multipliziert werden. Wenn beide Werte positiv sind, schneidet die Linie die Zelle nicht. Etwas Bit-Twiddling wandelt dann die Multiplikationen in ein Gesamtergebnis um.

Neil
quelle
1

Mathematica, 50 Bytes

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

Probieren Sie es online!

Nimmt m, n, c, a, bals Eingabe in dieser Reihenfolge.

Erklärung: Tuples@{{#,#+1},{#2,#2+1}}Erstellt eine Liste der Koordinaten der vier Ecken des Quadrats, nimmt dann das Skalarprodukt mit .{##4}(was bedeutet {#4, #5}) und addiert +#3Berechnungen ax + by + cfür x,yjede Ecke. Wenn die Linie durch den Punkt verläuft, ist dies Null. Wenn die Linie weiter vom Ursprung entfernt ist, ist sie negativ. und wenn die Linie näher am Ursprung liegt, ist sie positiv - daher prüfen wir das Signs dieser vier Werte. Die Linie verläuft genau dann außerhalb des Quadrats, wenn alle vier Werte 1 oder alle vier -1 sind. Wir überprüfen daher, ob ihre Summe genau zwischen -4 und 4 liegt.

(Diese Antwort ist vage inspiriert von meiner Antwort auf diese Frage .)

Kein Baum
quelle
1

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

Und ein großes Dankeschön an Leaky Nun!

TIO.

Daniel
quelle
131 Bytes
Undichte Nonne
121 Bytes
Undichte Nonne
@LeakyNun, wow super!
Daniel
114 Bytes
Undichte Nonne
110 Bytes
Undichte Nonne
1

Python , 54 Bytes

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

Probieren Sie es online!

(Danke an xnor für das Testskript.)

Wie es funktioniert

Die Linie geht genau dann durch m + 1/2 + x , n + 1/2 + y, wenn

a ⋅ ( m + 1/2 + x ) + b ⋅ ( n + 1/2 + y ) + c = 0
⇔ 2 ⋅ ( am + bn + c ) + a + b = -2 ⋅ ax - 2⋅ by .

Dies ist für einige möglich x |, | y | ≤ 1/2 , wenn und nur wenn | 2⋅ ( am + bn + c ) + a + b | ≤ | a | + | b |.

Anders Kaseorg
quelle
1

Java (OpenJDK 8) , 71 Byte

(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)

Probieren Sie es online!

Port der Python-Lösung von xnor.

Ursprüngliche Lösung unter Verwendung von Javas Form- / Linienschnittpunkt (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)

Probieren Sie es online!

Credits

Olivier Grégoire
quelle