|
Название задачи: Миротворцы . |
 |
Условие
N миротворцев из российского корпуса KFOR десантировались в окрестности аэропорта Слатина. Точка приземления каждого миротворца задается парой целочисленных координат (x, y). За один шаг каждый из десантников может переместиться на соседнюю целочисленную позицию вдоль оси X или Y (т.е. одна из его координат меняется на 1 по абсолютной величине). Шаги делаются по очереди, никакие два миротворца при этом не могут находиться в одной позиции одновременно.Десантники хотят выстроиться в шеренгу – линию, параллельную одной из
осей координат, в которой они стояли бы в подряд идущих целочисленных
позициях. Напишите программу, которая определяет минимальное суммарное
число шагов, необходимое миротворцам для того, чтобы образовать шеренгу.
Входные данные
Первая строка входного файла содержит целое число N – количество
миротворцев (1 ≤ N ≤ 10000). Каждая из последующих N строк содержит
координаты десантника – два целых числа из диапазона [-32768, 32767],
разделенные пробелом.
Выходные данные
Выведите в выходной файл искомое количество шагов.
Пример входного файла
3
-1 -1
0 0
1 1
Пример выходного файла
2
Решение
Скачать архив тестов и решенийПоскольку десантники могут перемещаться только вдоль координатных осей, то задачу можно решить отдельно по x-координатам и по y-координатам, а затем убедиться в том, что процесс перемещений можно организовать так, чтобы никакие два десантника ни в какой момент времени не находились бы в одной позиции. Тогда по одной координате мы должны за минимальное число ходов собрать десантников в одну точку, а по другой – выстроить в шеренгу.
Занумеруем десантников, расположенных на оси, в порядке возрастания их координаты. Назовем центром ту точку, где стоит десантник номер N div 2 + 1, если N нечетно, и любую точку между десантниками N div 2 и N div 2 + 1, если N четно. Тогда для сбора в одной точке следует выбрать любой из центров.
Пусть мы выстроили десантников в шеренгу. Заметим, что их взаимное расположение не поменялось (если один десантник стоял левее другого, то после построения это сохранилось, иначе число ходов не минимально). Если вычесть из координаты каждого десантника его номер, то все они окажутся в одной точке. Следовательно, для решения задачи построения в шеренгу нужно вычесть из координаты каждого десантника его номер, собрать всех десантников в одну точку и после прибавить номера обратно.
Перебрав два случая – когда десантники по оси X собираются в точку, а по оси Y строятся в шеренгу, и наоборот, – выберем из них тот, который требует меньшего числа шагов.
