Разделите первый квадрант (включая положительную ось x, положительную ось y и начало координат) на сетки 1x1, где каждая сетка помечена координатами ее нижнего левого угла, как показано ниже:
Обратите внимание, что каждая сетка содержит свои границы и вершины. Используя математические символы, сетка с меткой (m, n) будет представлять квадрат {(x,y) | m ≤ x ≤ m+1, n ≤ y ≤ n+1}
.
Для данной прямой линии в виде ax+by+c=0
целых чисел a
, b
и c
и сетки, представленной как (m,n)
, выведите, проходит ли линия через сетку, т.е. находится ли какая-либо точка в данной сетке на линии.
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
Пожалуйста, предложите больше тестов в комментариях.
Это код-гольф . Кратчайший ответ в байтах побеждает. Применяются стандартные лазейки .
code-golf
geometry
decision-problem
Дрянная Монахиня
источник
источник
[a, b, c]
(линия) и[m, n]
(квадрат)?Ответы:
Python 3,
8466 байтПервый гольф, первый провал (возможно).
Спасибо Роду за сокращение 18 байт с помощью функции вместо прямого ввода.
Попробуйте онлайн!
Объяснение:
В основном мы вычисляем значение функции строки для m и m + 1, если n находится между значениями, то список должен пройти через него в некоторой точке. Было бы намного лучше, если бы в языке был более простой способ ввода нескольких целых чисел.
источник
b
есть0
.Желе , 10 байт
Попробуйте онлайн!
Фон
Как и другие ответы перед моим, это зависит от того факта, что прямая линия делит плоскость на две полуплоскости. Прямоугольник либо содержится в одной из этих полуплоскостей (без пересечения с линией), либо пересекает обе полуплоскости (и, следовательно, линию, которая разделяет их.
Как это устроено
источник
Python 2 , 59 байт
Попробуйте онлайн!
Мы можем сказать, с какой стороны линии находится точка по признаку
a*x+b*y+c
. Линия проходит через квадрат (не считая касания), если все четыре вершины не(m,n),(m,n+1),(m+1,n),(m+1,n+1)
находятся строго на одной стороне линии. Мы можем вставить эти значения в извлечение константы,a*m+b*n+c
которая появляется во всех четырех:Таким образом, линия проходит через квадрат, если только эти четыре значения не являются положительными или отрицательными. Итак, достаточно, чтобы их минимум был,
<=0
а максимум был>=0
.Вычитание общего
a*m+b*n+c
из каждой части дает код.Немного более длинный подход состоит в том, чтобы проверить, имеет ли набор знаков (+, 0, -) длину по крайней мере 2.
Python 2 , 62 байта
Попробуйте онлайн!
источник
Mathematica,
6055 байт-5 байт спасибо @MartinEnder
форма ввода
источник
Solve
функция ...Пакетный, 66 байт
Пояснение: Мы рассматриваем значения, взятые уравнением в четырех углах ячейки. Если линия не пересекает ячейку, то все четыре значения имеют одинаковый знак, но если она пересекает ячейку, то хотя бы одно значение будет равно нулю или противоположному знаку. Сравнение упрощается умножением пар противоположных углов, тогда, если оба значения положительны, линия не пересекает ячейку. Некоторый сдвиг битов затем преобразует умножения в общий результат.
источник
Mathematica, 50 байтов
Попробуйте онлайн!
Принимает
m, n, c, a, b
как вход в этом порядке.Пояснение:
Tuples@{{#,#+1},{#2,#2+1}}
составляет список координат четырех углов квадрата, затем берет произведение точки с.{##4}
(что означает{#4, #5}
) и добавляет+#3
вычисленияax + by + c
дляx,y
каждого угла. Если линия проходит через точку, это ноль; если линия дальше от начала координат, она отрицательна; и если линия ближе к началу координат, она положительна - поэтому мы проверяемSign
s из этих четырех значений. Линия проходит вне квадрата, если и только если все четыре значения равны 1 или все четыре равны -1, поэтому мы проверяем, что их сумма строго находится в диапазоне от -4 до 4.(Этот ответ смутно вдохновлен моим ответом на этот вопрос .)
источник
Python 2,
147110 байтИ огромный спасибо Leaky Nun!
TIO.
источник
Python , 54 байта
Попробуйте онлайн!
(Спасибо xnor за тестовый скрипт.)
Как это устроено
Линия проходит через m + 1/2 + x , n + 1/2 + y тогда и только тогда, когда
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 .
Это возможно для некоторых | х |, | у | ≤ 1/2 тогда и только тогда, когда | 2⋅ ( a ⋅ m + b ⋅ n + c ) + a + b | ≤ | а | + | б |
источник
Java (OpenJDK 8) , 71 байт
Попробуйте онлайн!
Порт решения xnor Python.
Оригинальное решение, использующее встроенное пересечение формы / линии Java (108 байт)
Попробуйте онлайн!
кредиты
источник