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=0
mit 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 Code-Golf . Kürzeste Antwort in Bytes gewinnt. Es gelten Standardlücken .
quelle
[a, b, c]
(die Linie) und[m, n]
(das Quadrat)?Antworten:
Python 3,
8466 BytesErstes Golfen, zuerst scheitern (vielleicht).
Vielen Dank an Rod für das Abschneiden von 18 Bytes mithilfe einer Funktion anstelle der direkten Eingabe.
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.
quelle
b
ist0
.Gelee , 10 Bytes
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
quelle
Python 2 , 59 Bytes
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, diea*m+b*n+c
in allen vier vorkommt: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
<=0
und Maximum ist>=0
.Subtrahiert man das Gemeinsame
a*m+b*n+c
von 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
Probieren Sie es online!
quelle
Mathematica,
6055 Bytes-5 Bytes Danke an @MartinEnder
Eingabeformular
quelle
Solve
Funktion ...Batch, 66 Bytes
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.
quelle
Mathematica, 50 Bytes
Probieren Sie es online!
Nimmt
m, n, c, a, b
als 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+#3
Berechnungenax + by + c
fürx,y
jede 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 dasSign
s 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 .)
quelle
Python 2,
147110 BytesUnd ein großes Dankeschön an Leaky Nun!
TIO.
quelle
Python , 54 Bytes
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 ⋅ ( a ⋅ m + b ⋅ n + c ) + a + b = -2 ⋅ a ⋅ x - 2⋅ b ⋅ y .
Dies ist für einige möglich x |, | y | ≤ 1/2 , wenn und nur wenn | 2⋅ ( a ⋅ m + b ⋅ n + c ) + a + b | ≤ | a | + | b |.
quelle
Java (OpenJDK 8) , 71 Byte
Probieren Sie es online!
Port der Python-Lösung von xnor.
Ursprüngliche Lösung unter Verwendung von Javas Form- / Linienschnittpunkt (108 Bytes)
Probieren Sie es online!
Credits
quelle