11059. В поход!
В стране Смешариков новый сезон!
Теперь все они отправляются в поход. Для этого им нужно встретиться в одной
точке, и уже оттуда отправиться покорять мир. Лосяшу, координирующему действия
Смешариков, известны координаты всех участников похода. Помогите ему определить
какое минимальное количество секунд понадобится Смешарикам, чтобы собраться
всем вместе.
Изначально все Смешарики
находятся в узлах целочисленной сетки. Если Смешарик находится в точке (x, y),
то за одну секунду он может переместиться в точки (x, y + 1),
(x + 1, y), (x – 1, y)
или (x, y – 1), или же остаться в точке (x,
y).
Вход. В первой строке дано одно целое
число n (1 ≤ n ≤ 200000) – количество Смешариков.
Далее в n строках даны изначальные позиции Смешариков. Каждая позиция
описывается двумя целыми числами xi и yi
(-1018 ≤ xi, yi ≤ 1018).
Выход. Выведите минимальное количество
секунд, которое понадобится Смешарикам, чтобы собраться в одной точке.
|
Пример
входа 1 |
Пример
выхода 1 |
|
1 1 1 |
1 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
2 1 3 4 4 |
2 |
|
|
|
|
Пример
входа 3 |
Пример
выхода 3 |
|
3 0 0 3 3 0 3 |
3 |
РЕШЕНИЕ
геометрия
– преобразование координат
Анализ
алгоритма
Пусть Смешарик находится в точке
(x, y). Тогда за t секунд он сможет оказаться в любой целочисленной точке ромба как показано на рисунке.
Нам следует найти такое наименьшее натуральное t, для которого
все ромбы смешариков соответствующего размера будут иметь одну общую целочисленную точку. Рассмотрим третий
тест и отобразим ромбы каждого из трех смешариком для t
= 1, 2, 3.
При t = 3 смешарики, например, могут встретиться в точке (0, 3) или (1,
2).
Давайте повернем систему координат на -45 градусов
относительно центра координат. Ромбы перейдут в квадраты. Выведем формулы
поворота:
Или в декартовых координатах:
x’
+ iy’ = (x + iy) 
Избавимся от иррациональности, растянув картинку в 
раз.
Воспользуемся преобразованием:
Преобрзуем наши три точки:
·
(0, 0) → (0, 0)
·
(0, 3) → (3, 3)
·
(3, 3) → (6, 0)
Найдем координаты прямоугольника,
содержащего все точки (xi’, yi’) – преобразованные
начальные координаты смешариков. Пусть
·
minx
= min (xi’); maxx = max (xi’);
·
miny
= min (yi’); maxy
= max (yi’);
Прямоугольник с координатами
противоположных углов (minx, miny) – (maxx, maxy) содержит все
точки (xi’, yi’). При этом он является минимальным по площади, стороны
которого параллельны осям координат.
Для нашего примера таким
прямоугольником будет (0, 0) – (6, 3).
Точкой сбора смешариков (resx, resy) будет центр прямоугольника, а именно точка с координатами
(resx, resy) = 
Теперь следует найти наименьшее время, за которое все
смешарики смогут добраться из своих точек (xi’, yi’) в (resx,
resy). Для повернутого ромба –
квадрата в новой системе координат – растояние от (xi’, yi’) до точки (resx, resy) вычисляется по формуле:
max( | xi’ – resx |, | yi’ – resy |)
Все смешарики смогут добраться в (resx, resy) за время
Реализация алгоритма
Объявим константу бесконечность INFL.
typedef long long ll;
#define INFL (ll)4e18
Входные
точки храним в массиве inp.
vector<pair<ll, ll>> inp;
Функция
calc находит расстояние от точки (x, y) до самого дальнего смешарика. Преобразованные координаты
смешариков находятся в массиве inp.
ll calc(ll x, ll y)
{
ll res = 0;
for (auto p : inp)
res =
max(res, max(abs(p.first - x), abs(p.second - y)));
return res;
};
Основная
часть программы. Читаем входные данные.
cin >> n;
minx = INFL; maxx = -INFL; miny = INFL; maxy = -INFL;
for (i = 0; i < n; i++)
{
Читаем
исходные координаты смешарика (x, y). Совершаем поворот координатной
плоскости на -45 градусов. Запоминаем новые координаты в массиве inp.
cin >> x >> y;
nx = x + y;
ny = -x + y;
inp.push_back({ nx, ny });
Находим координаты прямоугольника
(minx, miny) – (maxx, maxy), содержащего все точки (xi’, yi’) – преобразованные координаты смешариков.
minx = min(minx, nx);
maxx = max(maxx, nx);
miny = min(miny, ny);
maxy = max(maxy, ny);
}
Находим точку сбора смешариков (resx, resy) – центр прямоугольника.
resx = (minx + maxx) / 2;
resy = (miny + maxy) / 2;
Вычисляем и выводим наименьшее время,
за которое все смешарики смогут добраться из своих точек (xi’, yi’) в (resx, resy).
ans = calc(resx, resy);
cout << ans << "\n";