Səfərə!#11059

Səfərə! (Həll təhlili)

Tutaq ki, Smeşarik $(x, y)$ nöqtəsində yerləşir. O zaman $t$ saniyə ərzində o şəkildə göstərildiyi kimi rombun istənilən tam ədədi nöqtəsinə çata bilər.

Hər bir Smeşarik üçün müvafiq ölçüdə olan rombaların bir ortaq tam ədədi nöqtəyə malik olacağı ən kiçik təbii $t$ -ni tapmaq lazımdır. Üçüncü testi nəzərdən keçirək və $t = 1, 2, 3$ t = 1, 2, 3 üçün üç Smeşarikə aid rombaları təsvir edək.

$t = 3$ t = 3 halında smeşariklər, məsələn, $(0, 3)$ və ya $(1, 2)$ nöqtəsində qovuşa bilər.

Koordinat sistemini mənfi $45°$ bucağı qədər qaynaq nöqtesindən döndərək şəkilləndirək. Bu çevirmədə rombalar kvadratlara çevriləcək. Çevirmə düsturlarını çıxaraq:

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

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

Və ya Dekart koordinatlarında:

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}

İrrasionalıqdan xilas olmaq üçün şəkili $2$ \sqrt{2} dəfə genişləndiririk. Bunun üçün aşağıdakı çevirmədən istifadə edək:

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

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

Üç nöqtəmizi çevirək:

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

Smeşariklərin çevrilmiş başlanğıc koordinatları olan bütün $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') nöqtələrini ehtiva edən düzbucaqlının koordinatlarını müəyyən edək. Mühayiyə edək:

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

Beləliklə, $(mi n_{x}, mi n_{y})$ (min_x, min_y) və $(ma x_{x}, ma x_{y})$ (max_x, max_y) əks künc nöqtələr olan düzbucaqlı bütün $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') nöqtələrini əhatə edəcəkdir. Hierbij is het de minimale oppervlakte van een rechthoek waarvan de zijden evenwijdig zijn met de coördinaatas.

In ons voorbeeld zal zo'n rechthoek $(0, 0) - (6, 3)$ (0, 0) - (6, 3) zijn.

Het verzamelpunt van de Smeşariks $(r e s_{x}, r e s_{y})$ (res_x, res_y) zal het centrum van dit rechthoek zijn, oftewel het punt met coördinaten

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

Nu moeten we de minimale tijd vinden waarin alle Smeshari's hun punten $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') kunnen bereiken naar het punt $(r e s_{x}, r e s_{y})$ (res_x, res_y). Voor de gedraaide diamant (vierkant in het nieuwe coördinatenstelsel) wordt de afstand van het punt $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') tot $(r e s_{x}, r e s_{y})$ (res_x, res_y) berekend met de formule:

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

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

Op deze manier kunnen alle Smeşariks zich in het punt $(r e s_{x}, r e s_{y})$ (res_x, res_y) verzamelen in een tijd die gelijk is aan de maximale van deze afstanden:

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)

Alqoritmin Hazırlanması

Çarpanla $I N F L$ dəyişənini təyin edək.

typedef lon uzun ll;
#define INFL (ll)4e18

Giriş nöqtələrini $in p$ massivində saxlayacağıq.

vektor<pair<ll, ll>> inp;

calc funksiyası ən uzaqda olan smeşarikdən $(x, y)$ nöqtəsinə qədər olan məsafəni hesablayır. Çevrilmiş smeşarik koordinatları $in p$ massivində yer alır.

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++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Smeşariklərin başlanğıc koordinatları $(x, y)$ oxuyuruq. Koordinat müstəvisini $- 45°$ bucağı qədər döndəririk və alınan koordinatları $in p$ massivində saxlayırıq.

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

Bundan sonra smeşariklərin çevrilmiş koordinatları olan bütün $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') nöqtələrini ehtiva edən $(mi n_{x}, mi n_{y})$ (min_x, min_y) və $(ma x_{x}, ma x_{y})$ (max_x, max_y) əks künc nöqtələr olan düzbucaqlının koordinatlarını tapırıq.

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

Smeşariklərin toplanacağı nöqtəni $(r e s_{x}, r e s_{y})$ (res_x, res_y) müəyyən edirik — bu cizgiliğın mərkəzi.

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

Bütün smeşariklərin öz nöqtələrindən $(x_{i}^{'}, y_{i}^{'})$ (x_i', y_i') $(r e s_{x}, r e s_{y})$ (res_x, res_y) nöqtəsinə çatması üçün lazım olan minimum vaxtı hesablayır və göstəririk.

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