@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;

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

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

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

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

Войти через центр авторизации
Похожие вопросы