Podziel pierwszą ćwiartkę (w tym dodatnią oś x, dodatnią oś y i początek) na siatki 1x1, przy czym każda siatka jest oznaczona współrzędnymi jej lewego dolnego rogu, jak pokazano poniżej:

Zauważ, że każda siatka zawiera swoje granice i wierzchołki. Używając symboli matematycznych, siatka oznaczona (m, n) reprezentuje kwadrat {(x,y) | m ≤ x ≤ m+1, n ≤ y ≤ n+1}.

Biorąc pod uwagę linię prostą w postaci ax+by+c=0liczb całkowitych a, bi csiatkę reprezentowaną przez (m,n), wypisz, czy linia przechodzi przez siatkę, tj. Czy którykolwiek punkt na danej siatce znajduje się na linii.

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

Proszę sugerować więcej przypadków testowych w komentarzach.

To jest golf golfowy . Najkrótsza odpowiedź w bajtach wygrywa. Obowiązują standardowe luki .

Python 3, 84 66 bajtów

Pierwszy golf, pierwszy porażka (może).

Dzięki Rod za golenie 18 bajtów za pomocą funkcji zamiast bezpośredniego wprowadzania.

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

Wypróbuj online!

Wyjaśnienie:

Zasadniczo obliczamy wartość funkcji liniowej dla m i m + 1, jeśli n jest pomiędzy wartościami, lista musi przez nią przejść w pewnym momencie. Byłoby znacznie lepiej, gdyby język miał prostszy sposób wprowadzania wielu liczb całkowitych.

Galaretka , 10 bajtów

ż‘{Œpæ.ṠE¬

Wypróbuj online!

tło

Podobnie jak inne odpowiedzi przed moimi, opiera się to na tym, że linia prosta dzieli płaszczyznę na dwie półpłaszczyzny. Prostokąt jest albo zawarty w jednej z tych półpłaszczyzn (brak przecięcia z linią), albo przecina oba półpłaszczyzny (a zatem linię, która je oddziela.

Jak to działa

ż‘{Œ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 bajtów

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

Wypróbuj online!

Po znaku możemy rozpoznać, po której stronie linii jest punkt a*x+b*y+c. Linia przechodzi przez kwadrat (licząc dotykając), chyba że wszystkie cztery wierzchołki (m,n),(m,n+1),(m+1,n),(m+1,n+1)znajdują się dokładnie po tej samej stronie linii. Możemy podłączyć te wartości w ekstrakcie stałej, a*m+b*n+cktóra pojawia się we wszystkich czterech:

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

Tak więc linia przechodzi przez kwadrat, chyba że wszystkie te cztery wartości są dodatnie lub wszystkie ujemne. Wystarczy więc ich minimum <=0i maksimum >=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)

Odejmowanie części wspólnej a*m+b*n+cod każdej części daje kod.

Nieco dłuższym podejściem jest sprawdzenie, czy zestaw znaków (+, 0, -) ma długość co najmniej 2.

Python 2 , 62 bajty

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

Wypróbuj online!

Mathematica, 60 55 bajtów

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

-5 bajtów dzięki na @MartinEnder

formularz wejściowy

[a, b, c, m, n]

Partia, 66 bajtów

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

Objaśnienie: Rozważamy wartości przyjęte przez równanie w czterech rogach komórki. Jeśli linia nie przecina komórki, wszystkie cztery wartości mają ten sam znak, ale jeśli przecina komórkę, to co najmniej jedna wartość będzie równa zero lub znak przeciwny. Porównanie upraszcza się, mnożąc pary przeciwległych narożników, a jeśli obie wartości są dodatnie, to linia nie przecina komórki. Niektóre kręcenie bitów przekształca następnie mnożenia w ogólny wynik.

Mathematica, 50 bajtów

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

Wypróbuj online!

Trwa m, n, c, a, b dane wejściowe w tej kolejności.

Objaśnienie: Tuples@{{#,#+1},{#2,#2+1}}tworzy listę współrzędnych czterech rogów kwadratu, a następnie bierze iloczyn skalarny za pomocą .{##4}(co oznacza {#4, #5}) i dodaje +#3obliczenia ax + by + cdla x,ykażdego rogu. Jeśli linia przechodzi przez punkt, jest to zero; jeśli linia jest dalej od początku, jest ujemna; a jeśli linia jest bliżej początku, jest dodatnia - dlatego sprawdzamy Signs tych czterech wartości. Linia przechodzi poza kwadrat wtedy i tylko wtedy, gdy wszystkie cztery wartości są równe 1 lub wszystkie cztery są równe -1, więc sprawdzamy, czy ich suma wynosi dokładnie od -4 do 4.

(Ta odpowiedź jest niejasno zainspirowana moją odpowiedzią na to pytanie ).

Python 2, 147 110 bajtów

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

I wielkie podziękowania dla Dziurawej Zakonnicy!

TIO.

Python , 54 bajty

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

Wypróbuj online!

(Dzięki xnor za skrypt testowy.)

Jak to działa

Linia przechodzi przez m + 1/2 + x , n + 1/2 + y wtedy i tylko wtedy

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 .

Jest to możliwe dla niektórych | x |, | y | ≤ 1/2 wtedy i tylko wtedy, gdy | 2⋅ ( a ⋅ m + b ⋅ n + c ) + a + b | ≤ | a | + | b |

Java (OpenJDK 8) , 71 bajtów

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

Wypróbuj online!

Rozwiązanie Xnor's Python.

Oryginalne rozwiązanie, wykorzystujące wbudowane przecięcie kształtu / linii Java (108 bajtów)

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

Wypróbuj online!

Kredyty

• -8 bajtów dzięki pułapowi cat