Требуется минимизировать количество точек с хотя бы одной целочисленной координатой на линии. Как это сделать?

Question

[Sheephard]

У меня есть координаты двух точек. Мне требуется провести между ними ломаную так, что бы количество пересечений этой ломаной с координатами, где хотя бы одна из них — целая, были сведены к минимуму. Как я могу это сделать и как мне найти количество этих точек пересечения?

Вот кусок кода, который, по идее, должен был это делать:

rx = x1 - x0
ry = y1 - y0

if abs(rx) < abs(ry):
    res.append(abs(ry) + 1)
else:
     res.append(abs(rx) + 1)
k += 1

х0 и х1 — координаты первой, а у0 и у1 — координаты второй точки.
В res, по задумке, у меня должен быть ответ (кладу ответы в список, т.к. точек может быть несколько).
Заранее благодарю за любую помощь.

Comments

[Vindicar]

количество пересечений этой ломаной с координатами, где хотя бы одна из них — целая, были сведены к минимуму

Пример можно?

[Sheephard]

Vindicar, конечно. Например для таких двух точек:
(-2, -0.5) (0.5, 1.5)
ответом будет число 3.
А для точек
(0, -2) (0, 2)
— число 5.

Answer 1

[Wataru]

Представьте сетку вдоль целых координат. Ваши две точки в каких-то ячейках. Чтобы перейти из одной ячейки в соседнюю придется пересечь границу - это будет считаемая точка.

Т.е. вам надо найти путь из одной клетки в другую, пройдя по как можно меньшему количеству клеток. Можно ходить в 8 направлений - если пересечь угол, то можно за одну точку на ломаной перейти по диагонали.

Немного порисовав вы поймёте, что ответ - миксимум из горизонтального и вертикального расстояний между начальной и конечной клетками.

Надо только аккуратно разобрать случаи, если начальная или конечная точка лежит на границе клетки.

Comments

[Sheephard]

Спасибо за ответ!