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=0
liczb całkowitych a
, b
i c
siatkę 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 .
code-golf
geometry
decision-problem
Leaky Nun
źródło
źródło
[a, b, c]
(linia) i[m, n]
(kwadrat)?Odpowiedzi:
Python 3,
8466 bajtówPierwszy golf, pierwszy porażka (może).
Dzięki Rod za golenie 18 bajtów za pomocą funkcji zamiast bezpośredniego wprowadzania.
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.
źródło
b
jest0
.Galaretka , 10 bajtów
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
źródło
Python 2 , 59 bajtów
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+c
która pojawia się we wszystkich czterech:Tak więc linia przechodzi przez kwadrat, chyba że wszystkie te cztery wartości są dodatnie lub wszystkie ujemne. Wystarczy więc ich minimum
<=0
i maksimum>=0
.Odejmowanie części wspólnej
a*m+b*n+c
od 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
Wypróbuj online!
źródło
Mathematica,
6055 bajtów-5 bajtów dzięki na @MartinEnder
formularz wejściowy
źródło
Solve
funkcję ...Partia, 66 bajtów
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.
źródło
Mathematica, 50 bajtów
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+#3
obliczeniaax + by + c
dlax,y
każ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 sprawdzamySign
s 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 ).
źródło
Python 2,
147110 bajtówI wielkie podziękowania dla Dziurawej Zakonnicy!
TIO.
źródło
Python , 54 bajty
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 |
źródło
Java (OpenJDK 8) , 71 bajtów
Wypróbuj online!
Rozwiązanie Xnor's Python.
Oryginalne rozwiązanie, wykorzystujące wbudowane przecięcie kształtu / linii Java (108 bajtów)
Wypróbuj online!
Kredyty
źródło