У похід!#11059

У похід! (Розбір)

Нехай Смішарик знаходиться в точці $(x, y)$ . Тоді за $t$ секунд він зможе опинитися в будь-якій цілочисельній точці ромбу, як показано на рисунку.

Потрібно знайти найменше натуральне $t$ , при якому всі ромби відповідного розміру для кожного Смішарика матимуть хоча б одну спільну цілочисельну точку. Розглянемо третій тест і зобразимо ромби для трьох Смішариків при $t = 1, 2, 3$ t = 1, 2, 3.

При $t = 3$ t = 3 смішарики, наприклад, можуть зустрітися в точці $(0, 3)$ або $(1, 2)$ .

Обертаймо систему координат на $- 45°$ відносно початку координат. При такому перетворенні ромби перетворяться у квадрати. Виведемо формули обертання:

z^{'} = z e^{- i \frac{π}{4}}

z' = ze^{-i\frac{\pi}{4}}

Або в декартових координатах:

x^{'} + i y^{'} = (x + i y) \cdot (cos (\frac{π}{4}) - i sin (\frac{π}{4}))

x' + iy' = (x + iy) \cdot (\cos\left(\frac{\pi}{4}\right) - i\sin\left(\frac{\pi}{4}\right))

{x^{'} = x \frac{2}{2} + y \frac{2}{2} y^{'} = - x \frac{2}{2} + y \frac{2}{2}

\begin{cases} x' = x\frac{\sqrt{2}}{2} + y\frac{\sqrt{2}}{2} \\ y' = -x\frac{\sqrt{2}}{2} + y\frac{\sqrt{2}}{2} \end{cases}

Позбудемося ірраціональності, розтягнувши зображення в $2$ \sqrt{2} рази. Для цього скористаємося наступним перетворенням:

{x^{'} = x + y y^{'} = - x + y

\begin{cases} x' = x + y \\ y' = -x + y \end{cases}

Преобразуємо наші три точки:

$(0, 0) \to (0, 0)$ (0, 0) → (0, 0)
$(0, 3) \to (3, 3)$ (0, 3) → (3, 3)
$(3, 3) \to (6, 0)$ (3, 3) → (6, 0)

Знайдемо координати прямокутника, що містить усі точки $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') — перетворені початкові координати смішариків. Позначимо:

$mi n_{x} = min (x_{i}^{'}); ma x_{x} = ma x (x_{i}^{'})$ min_x = min (x_i'); max_x = max (x_i');
$mi n_{y} = min (y_{i}^{'}); ma x_{y} = ma x (y_{i}^{'})$ min_y = min (y_i'); max_y = max (y_i');

Тоді прямокутник з протилежними кутами $(mi n_{x}, mi n_{y})$ (min_x, min_y) та $(ma x_{x}, ma x_{y})$ (max_x, max_y) містить усі точки $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i'). При цьому він є мінімальним за площею прямокутником, сторони якого паралельні осям координат.

У нашому прикладі таким прямокутником буде $(0, 0) - (6, 3)$ (0, 0) - (6, 3).

Точкою збору смішариків $(r e s_{x}, r e s_{y})$ (res_x, res_y) буде центр цього прямокутника, тобто точка з координатами

(r e s_{x}, r e s_{y}) = (\frac{mi n _{x} + ma x _{x}}{2}, \frac{mi n _{y} + ma x _{y}}{2})

(res_x, res_y) = \left(\frac{min_x + max_x}{2}, \frac{min_y + max_y}{2}\right)

Тепер потрібно знайти мінімальний час, за який усі Смішарики зможуть дістатися з їхніх точок $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') до точки $(r e s_{x}, r e s_{y})$ (res_x, res_y). Для повернутого ромба (квадрата в новій системі координат) відстань від точки $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') до $(r e s_{x}, r e s_{y})$ (res_x, res_y) обчислюється за формулою:

ma x (∣ x_{i}^{'} - r e s_{x} ∣, ∣ y_{i}^{'} - r e s_{y} ∣)

max( | x_i' - res_x |, | y_i' - res_y |)

Таким чином, усі Смішарики зможуть зібратися в точці $(r e s_{x}, r e s_{y})$ (res_x, res_y) за час, рівний максимальному з цих відстаней:

1 \leq i \leq n max (ma x (∣ x_{i}^{'} - r e s_{x} ∣, ∣ y_{i}^{'} - r e s_{y} ∣))

\max_{1 \le i \le n}\left( max( | x_i' - res_x |, | y_i' - res_y |) \right)

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

Оголосимо константу нескінченність $I N F L$ .

typedef long long ll;
#define INFL (ll)4e18

Вхідні точки будемо зберігати в масиві $in p$ .

vector<pair<ll, ll>> inp;

Функція calc обчислює відстань від точки $(x, y)$ до найвіддаленішого Смішарика. Перетворені координати Смішариків знаходяться в масиві $in p$ .

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

C++

Основна частина програми. Читаємо вхідні дані.

cin >> n;
minx = INFL; maxx = -INFL; miny = INFL; maxy = -INFL;
for (i = 0; i < n; i++)
{

Читаємо вихідні координати Смішарика $(x, y)$ . Виконуємо поворот координатної площини на $- 45°$ і зберігаємо отримані координати в масиві $in p$ .

  cin >> x >> y;
  nx = x + y;
  ny = -x + y;
  inp.push_back({ nx, ny });

Після цього знаходимо координати прямокутника з протилежними кутами $(mi n_{x}, mi n_{y})$ (min_x, min_y) і $(ma x_{x}, ma x_{y})$ (max_x, max_y), який містить усі точки $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') — перетворені координати Смішариків.

  minx = min(minx, nx);
  maxx = max(maxx, nx);
  miny = min(miny, ny);
  maxy = max(maxy, ny);
}

Визначаємо точку збору Смішариків $(r e s_{x}, r e s_{y})$ (res_x, res_y) — центр прямокутника.

resx = (minx + maxx) / 2;
resy = (miny + maxy) / 2;

Обчислюємо і виводимо мінімальний час, необхідний для того, щоб усі Смішарики змогли дістатися з їхніх точок $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') до точки $(r e s_{x}, r e s_{y})$ (res_x, res_y).

ans = calc(resx, resy);
cout << ans << "\n";