С++ СИРИУС Отрезок Какое количество клеток пересекает отрезок на клетчатой бумаге, соединяющий точки с координатами

Отрезок:

Инструкция:
Для решения данной задачи необходимо определить, сколько клеток пересекает отрезок на клетчатой бумаге, соединяющий две заданные точки с координатами (a,b) и (c,d).

Отрезок считается проходящим через клетку, если он пересекает ее границу или проходит через ее центр. Иначе говоря, если координаты его концов лежат по разные стороны от границ клетки или попадают на границу.

Для решения задачи можно воспользоваться формулой Брезенхэма, которая позволяет определить координаты всех точек, которые лежат на прямой между двумя заданными точками. Затем необходимо посчитать количество клеток, в которых лежат эти точки.

Пример:
Входные данные: 0 0 2 3
Отрезок соединяет точку (0,0) и точку (2,3).

Шаг 1: Отрезок проходит через клетку (0,0).
Шаг 2: Отрезок проходит через клетку (1,1).
Шаг 3: Отрезок проходит через клетку (2,2).
Шаг 4: Отрезок не проходит через клетку (2,3).

Ответ: Отрезок пересекает 3 клетки.

Совет:
При решении данной задачи полезно использовать графическую интерпретацию и рисовать отрезок и клетки на бумаге, чтобы визуализировать процесс пересечения и определения количества клеток, которые пересекает отрезок.

Задача на проверку:
Сколько клеток пересекает отрезок на клетчатой бумаге, соединяющий точки с координатами (3,5) и (9,2)?