On a hike!#11059

On a hike! (Editorial)

Let a Smesharik be at the point $(x, y)$ . Then in $t$ seconds, it can reach any integer point inside the diamond, as shown in the figure.

It is required to find the smallest positive integer $t$ such that the diamonds of the corresponding size for each Smesharik will all have at least one common integer point. Let us consider the third test and illustrate the diamonds for the three Smeshariks at $t = 1, 2, 3$ t = 1, 2, 3.

For $t = 3$ t = 3, the Smeshariks can, for example, meet at the point $(0, 3)$ or $(1, 2)$ .

Let us rotate the coordinate system by $- 45°$ relative to the origin. Under this transformation, the diamonds will turn into squares. Let us write down the rotation formulas:

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

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

Or, in Cartesian coordinates:

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}

Let us eliminate the irrationality by stretching the image by a factor of $2$ \sqrt{2}. To do this, we use the following transformation:

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

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

Now let us transform our three points:

$(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)

Let us find the coordinates of the rectangle containing all the points $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') — the transformed initial coordinates of the Smeshariks. Denote:

$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');

Then the rectangle with opposite corners $(mi n_{x}, mi n_{y})$ (min_x, min_y) and $(ma x_{x}, ma x_{y})$ (max_x, max_y) contains all the points $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i'). Moreover, it is the minimum area rectangle whose sides are parallel to the coordinate axes.

In our example, such a rectangle is $(0, 0) - (6, 3)$ (0, 0) - (6, 3).

The meeting point of the Smeshariks $(r e s_{x}, r e s_{y})$ (res_x, res_y) will be the center of this rectangle, that is, the point with coordinates

(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)

Now we need to find the minimum time in which all the Smeshariks can reach the point $(r e s_{x}, r e s_{y})$ (res_x, res_y) from their positions $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i'). For the rotated diamond (a square in the new coordinate system), the distance from the point $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') to $(r e s_{x}, r e s_{y})$ (res_x, res_y) is calculated using the formula:

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

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

Thus, all the Smeshariks will be able to gather at the point $(r e s_{x}, r e s_{y})$ (res_x, res_y) in a time equal to the maximum of these distances:

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)

Algorithm implementation

Let us define the constant infinity $I N F L$ .

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

Store the input points in the array $in p$ .

vector<pair<ll, ll>> inp;

The function calc computes the distance from the point $(x, y)$ to the farthest Smesharik. The transformed coordinates of the Smeshariks are stored in the array $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++

The main part of the program. Read the input data.

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

Read the initial coordinates of the Smesharik $(x, y)$ . Perform a $- 45°$ rotation of the coordinate plane and store the resulting coordinates in the array $in p$ .

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

After that, find the coordinates of the rectangle with opposite corners $(mi n_{x}, mi n_{y})$ (min_x, min_y) and $(ma x_{x}, ma x_{y})$ (max_x, max_y), which contains all the points $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') — the transformed coordinates of the Smeshariks.

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

Determine the meeting point of the Smeshariks $(r e s_{x}, r e s_{y})$ (res_x, res_y) — the center of the rectangle.

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

Compute and print the minimum time required for all the Smeshariks to reach the point $(r e s_{x}, r e s_{y})$ (res_x, res_y) from their positions $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i').

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