Футбол#498

Футбол (Editorial)

Автор: Андрій Холод

Роздробник: Павло Цікалишин

Розбір підготовано: Костянтин Денисов

Щоб забити гол, достатньо влучити в будь-яку точку воріт, тобто мінімізувати $∣ x - x_{v} ∣ + ∣ y - y_{v} ∣$ |x-x_v|+|y-y_v| по всіх $y \in [y_{1}, y_{2}]$ y \in [y_1,y_2].

Частина $∣ x - x_{v} ∣$ |x-x_v| не залежить від $y$ , тому мінімізувати треба лише $∣ y - y_{v} ∣$ |y-y_v| на відрізку $[y_{1}, y_{2}]$ [y_1,y_2]. Мінімальна відстань від точки $y_{v}$ y_v до відрізка $[y_{1}, y_{2}]$ [y_1,y_2] дорівнює:

$0$ , якщо $y_{1} \leq y_{v} \leq y_{2}$ y_1 \le y_v \le y_2,
$y_{1} - y_{v}$ y_1-y_v, якщо $y_{v} < y_{1}$ y_v < y_1,
$y_{v} - y_{2}$ y_v-y_2, якщо $y_{v} > y_{2}$ y_v > y_2.

Це можна записати одним рядком як $d_{y} = max (0, y_{1} - y_{v}, y_{v} - y_{2})$ d_y = \max(0,\, y_1-y_v,\, y_v-y_2).

Тоді відповідь: $p_{m i n} = ∣ x - x_{v} ∣ + d_{y}$ p_{\min} = |x-x_v| + d_y.

Складність. Час: $O (1)$ , пам'ять: $O (1)$ .

∣ x - x_{v} ∣ + ∣ y - y_{v} ∣

y \in [y_{1}, y_{2}]

∣ x - x_{v} ∣

∣ y - y_{v} ∣

[y_{1}, y_{2}]

y_{v}

[y_{1}, y_{2}]

y_{1} \leq y_{v} \leq y_{2}

y_{1} - y_{v}

y_{v} < y_{1}

y_{v} - y_{2}

y_{v} > y_{2}

d_{y} = max (0, y_{1} - y_{v}, y_{v} - y_{2})

p_{m i n} = ∣ x - x_{v} ∣ + d_{y}