как посчитать кол-во целых точек лежащие на прямой
Мне нужно найти кол-во точек, которые лежат внутри треугольника ABC с координатами (x,y).
Эту задачу можно решить через формулу Пика, но я столкнулся с проблемой. Я не знаю, как посчитать кол-во целых точек, которые лежат на прямых.
Подскажите пожалуйста, как это сделать( найти кол-во целых точек, которые лежат на прямых, а не внутри треугольника )
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Если абсолютные значения разностей целочисленных координат концов отрезка равны dx и dy, то на отрезке лежит GCD(dx, dy) + 1 целочисленных точек, включая концы. (GCD - НОД, наибольший общий делитель).
Для замкнутого многоугольника, чтобы не учитывать вершины дважды, единицу можно убрать.