Czy ta linia przechodzi przez ten kwadrat?

19

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 . Najkrótsza odpowiedź w bajtach wygrywa. Obowiązują standardowe luki .

Leaky Nun
źródło
1
Oczywiście powinniśmy być w stanie założyć, że nie oba a i b są równe 0, ponieważ wtedy c wynosi zero, mogą istnieć linie nieskończone, a jeśli c jest różna od zera, nie może być żadnej linii.
Erik the Outgolfer
Czy mogę uzyskać dane wejściowe jako dwie lub więcej tablic, powiedzmy [a, b, c](linia) i [m, n](kwadrat)?
Erik the Outgolfer
@EriktheOutgolfer Jestem zaskoczony, że nie ma meta.
Leaky Nun
Powiązane
Nie drzewo,
Silnie powiązane .
Olivier Grégoire

Odpowiedzi:

5

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.

niewzruszony
źródło
2
Witamy w PPCG!
betseg
1
Czy nie musi to sprawdzać względem n + 1, a także m + 1?
Neil
3
Dziel przez zero, kiedy bjest 0.
Olivier Grégoire
Ponadto nie przechodzi kilku przypadków testowych wyróżnionych przez Dziurawą Zakonnicę.
Olivier Grégoire
5

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.
Dennis
źródło
4

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!

xnor
źródło
3

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]

J42161217
źródło
2
Ach, chciałbym, żeby każdy język miał jakąś Solvefunkcję ...
Erik, Outgolfer,
3

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.

Neil
źródło
1

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

Nie drzewo
źródło
1

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.

Daniel
źródło
131 bajtów
Leaky Nun
121 bajtów
Leaky Nun
@LeakyNun, wow niesamowite!
Daniel
114 bajtów
Leaky Nun
110 bajtów
Leaky Nun
1

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⋅ ( am + bn + c ) + a + b = -2⋅ ax - 2⋅ b y .

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

Anders Kaseorg
źródło
1

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

Olivier Grégoire
źródło