Задать вопрос
@dmitrii2004

Через сколько клеток проходит отрезок?

Отрезок
На клетчатой бумаге нарисовали отрезок, соединяющий точки с координатами (a,b) и (c,d). Через сколько клеток проходит этот отрезок (считается, что отрезок проходит через клетку, если он проходит через её внутренность, если же он проходит только через вершину или по границе клетки, считается, что он не проходит через клетку)?

Входные данные

Программа получает на вход четыре целых числа, записанных в одной строке: a,b,c,d. Все числа по модулю не превосходят 106.

Выходные данные

Выведите ответ на задачу.
Примеры
Ввод
0 0 6 4
Вывод
8
Помогите пожалуйста сайт при выполнении программы пишет неверный ответ
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
int main()
{
	 long long a, b, c, d, x, y, g = 1, x1, y1, k;
	cin >> a >> b >> c >> d;
	x = abs(a - c);
	y = abs(b - d);
	for (int i = 1; i <= min(x, y); i++)
	{
		if (x % i == 0 and y % i == 0)
		{
			g = i;
		}
	}
	x1 = x / g;
	y1 = y / g;
	k = x1 + y1 - 1;
	cout << g * k;

}
  • Вопрос задан
  • 1818 просмотров
Подписаться 1 Простой Комментировать
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Проблема в том, что GCD(0,1000) = 1000. А у вас цикл ни разу не выполнится и не найдет ничего.

Ваше решение не работет, если отрезок вертикальный или горизонтальный. Ответ должен быть 0, вы же выведите что-то другое.

Но, когда вы это исправите, ваше решение скорее всего не пройдет по времени. Ищите наибольший общий делитель алгоритмом евклида.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@KingstonKMS
Находишь наибольший общий делитель dX и dY и вычитаешь его из суммы dX и dY
6 + 4 - 2 = 8
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы