Эта линия проходит через этот квадрат?

19

Разделите первый квадрант (включая положительную ось 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

Пожалуйста, предложите больше тестов в комментариях.


Это . Кратчайший ответ в байтах побеждает. Применяются стандартные лазейки .

Дрянная Монахиня
источник
1
Конечно, мы должны быть в состоянии предположить, что не оба a и b равны 0, так как тогда, если c равно нулю, могут быть бесконечные строки, в то время как если c ненулевое, вообще не может быть никакой строки.
Эрик Outgolfer
Могу ли я получить входные данные в виде двух или более массивов, скажем [a, b, c](линия) и [m, n](квадрат)?
Эрик Outgolfer
@EriktheOutgolfer Я удивлен, что не в мета.
Утренняя монахиня
Связанный
Не дерево
Сильно связаны .
Оливье Грегуар

Ответы:

5

Python 3, 84 66 байт

Первый гольф, первый провал (возможно).

Спасибо Роду за сокращение 18 байт с помощью функции вместо прямого ввода.

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

Попробуйте онлайн!

Объяснение:

В основном мы вычисляем значение функции строки для m и m + 1, если n находится между значениями, то список должен пройти через него в некоторой точке. Было бы намного лучше, если бы в языке был более простой способ ввода нескольких целых чисел.

irapsaged
источник
2
Добро пожаловать в PPCG!
betseg
1
Разве для этого не нужно проверять как n + 1, так и m + 1?
Нил
3
Деление на ноль, когда bесть 0.
Оливье Грегуар
Кроме того, он не проходит несколько тестовых случаев, выделенных Leaky Nun.
Оливье Грегуар
5

Желе , 10 байт

ż‘{Œpæ.ṠE¬

Попробуйте онлайн!

Фон

Как и другие ответы перед моим, это зависит от того факта, что прямая линия делит плоскость на две полуплоскости. Прямоугольник либо содержится в одной из этих полуплоскостей (без пересечения с линией), либо пересекает обе полуплоскости (и, следовательно, линию, которая разделяет их.

Как это устроено

ż‘{Œ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.
Деннис
источник
4

Python 2 , 59 байт

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

Попробуйте онлайн!

Мы можем сказать, с какой стороны линии находится точка по признаку a*x+b*y+c. Линия проходит через квадрат (не считая касания), если все четыре вершины не (m,n),(m,n+1),(m+1,n),(m+1,n+1)находятся строго на одной стороне линии. Мы можем вставить эти значения в извлечение константы, a*m+b*n+cкоторая появляется во всех четырех:

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а максимум был >=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)

Вычитание общего a*m+b*n+c из каждой части дает код.

Немного более длинный подход состоит в том, чтобы проверить, имеет ли набор знаков (+, 0, -) длину по крайней мере 2.

Python 2 , 62 байта

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

Попробуйте онлайн!

XNOR
источник
3

Mathematica, 60 55 байт

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

-5 байт спасибо @MartinEnder

форма ввода

[А, б, в, м, н]

J42161217
источник
2
Ах, я бы хотел, чтобы у каждого языка была Solveфункция ...
Эрик Аутгольфер
3

Пакетный, 66 байт

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

Пояснение: Мы рассматриваем значения, взятые уравнением в четырех углах ячейки. Если линия не пересекает ячейку, то все четыре значения имеют одинаковый знак, но если она пересекает ячейку, то хотя бы одно значение будет равно нулю или противоположному знаку. Сравнение упрощается умножением пар противоположных углов, тогда, если оба значения положительны, линия не пересекает ячейку. Некоторый сдвиг битов затем преобразует умножения в общий результат.

Нил
источник
1

Mathematica, 50 байтов

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

Попробуйте онлайн!

Принимает m, n, c, a, bкак вход в этом порядке.

Пояснение: Tuples@{{#,#+1},{#2,#2+1}}составляет список координат четырех углов квадрата, затем берет произведение точки с .{##4}(что означает {#4, #5}) и добавляет +#3вычисления ax + by + cдля x,yкаждого угла. Если линия проходит через точку, это ноль; если линия дальше от начала координат, она отрицательна; и если линия ближе к началу координат, она положительна - поэтому мы проверяем Signs из этих четырех значений. Линия проходит вне квадрата, если и только если все четыре значения равны 1 или все четыре равны -1, поэтому мы проверяем, что их сумма строго находится в диапазоне от -4 до 4.

(Этот ответ смутно вдохновлен моим ответом на этот вопрос .)

Не дерево
источник
1

Python 2, 147 110 байт

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

И огромный спасибо Leaky Nun!

TIO.

Даниил
источник
131 байт
Leaky Nun
121 байт
Утренняя монахиня
@ LeakyNun, ничего себе!
Даниэль
114 байт
Утренняя монахиня
110 байт
Утренняя монахиня
1

Python , 54 байта

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

Попробуйте онлайн!

(Спасибо xnor за тестовый скрипт.)

Как это устроено

Линия проходит через m + 1/2 + x , n + 1/2 + y тогда и только тогда, когда

a ⋅ ( m + 1/2 + x ) + b ⋅ ( n + 1/2 + y ) + c = 0
⇔ 2⋅ ( am + bn + c ) + a + b = −2⋅ ax - 2⋅ by .

Это возможно для некоторых | х |, | у | ≤ 1/2 тогда и только тогда, когда | 2⋅ ( am + bn + c ) + a + b | ≤ | а | + | б |

Андерс Касеорг
источник
1

Java (OpenJDK 8) , 71 байт

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

Попробуйте онлайн!

Порт решения xnor Python.

Оригинальное решение, использующее встроенное пересечение формы / линии Java (108 байт)

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

Попробуйте онлайн!

кредиты

Оливье Грегуар
источник