10405. Телепортация

Одна из сельскохозяйственных работ, которые фермер Джон не любит больше всего, – это таскать много коровьего навоза. Чтобы упростить этот процесс, он придумал гениальное изобретение: телепорт навоза! Вместо того, чтобы перевозить навоз между двумя точками в тележке позади трактора, он может использовать телепорт для навоза, чтобы мгновенно транспортировать навоз из одного места в другое.

Ферма Джона построена вдоль одной длинной прямой дороги, поэтому любое место на его ферме можно описать положением на этой дороге (точкой на числовой прямой). Телепорт описывается двумя числами x и y, где навоз, доставленный в точку x, может быть мгновенно доставлен в точку y, и наоборот.

Фермер Джон хочет транспортировать навоз из места a в место b, и он построил телепорт, который может быть полезен во время этого процесса (если телепорт не поможет, то его можно не использовать). Помогите ему определить минимальное общее расстояние, на которое следует перевезти навоз с помощью трактора.

Вход. Одна строка содержит четыре целых числа: a и b, описывающие начальную и конечную точки, за которыми следуют x и y, описывающие телепорт. Все позиции являются целыми числами в диапазоне 0 ... 100, и они не обязательно отличаются друг от друга.

Выход. Выведите одно целое число – минимальное расстояние, на которое фермер Джон должен возить навоз на своем тракторе.

Пример входа	Пример выхода
3 10 8 2	3

РЕШЕНИЕ

математика

Анализ алгоритма

У фермера Джона имеются следующие варианты передвижения навоза:

· Напрямую от a до b, будет пройдено расстояние |a – b|;

· Везти на тракторе от a до x, телепортировать от x до y, и снова везти на тракторе от y до b. Суммарно трактором будет пройдено расстояние |a – x| + |b – y|;

· Везти на тракторе от a до y, телепортировать от y до x, и снова везти на тракторе от x до b. Суммарно трактором будет пройдено расстояние |a – y| + |b – x|;

Наименьшее из этих трех значений и будет ответом.

Пример

В приведенном примере лучшая стратегия – переместить навоз из позиции 3 в позицию 2, телепортировать его в позицию 8, а затем переместить в позицию 10. Общее расстояние, которое проедет трактор, составит 1 + 2 = 3.

Реализация алгоритма

Читаем входные данные.

scanf("%d %d %d %d", &a, &b, &x, &y);

Вычисляем ответ – минимум среди трех значений.

res = abs(a - b);

res = min(res, abs(a - x) + abs(b - y));

res = min(res, abs(a - y) + abs(b - x));

Выводим ответ.

printf("%d\n", res);

Python реализация

Читаем входные данные.

a, b, x, y = map(int, input().split())

Вычисляем ответ – минимум среди трех значений.

res = abs(a - b)

res = min(res, abs(a - x) + abs(b - y))

res = min(res, abs(a - y) + abs(b - x))

Выводим ответ.

print(res)