[AtCoder] ABC 178 E – Dist Max
問題
方針
点 \( i \) と点 \( j \) のマンハッタン距離を \( d(i, j) = |x_i – x_j| + |y_i – y_j|\) とすると、絶対値の外し方を考慮して、
\begin{eqnarray}
\max(x_i – x_j + y_i – y_j, x_i – x_j – (y_i – y_j), -(x_i- x_j) + y_i – y_j, -(x_i – x_j) – (y_i – y_j))\\
\end{eqnarray}
と表すことができます。上記を \( i, j \) について整理すると、
\[ \max(x_i + y_i – (x_j + y_j), x_i – y_i – (x_j – y_j), -(x_i – y_i) + x_j – y_j, -(x_i + y_i) + x_j + y_j)\]
となります。ここで、\( t_i = x_i + y_i , u_i = x_i – y_i\) とすると、
\[ d(i, j) = \max(t_i – t_j, u_i- u_j, t_i – u_j, -t_i + u_j)\]
となります。\( i \) と \( j \) が分離されているので、任意の \( i \neq j \) を満たす任意の \( t_i, t_j, u_i, u_j \) を選ぶことができます。ここで、\( a = \max(t_i), b = \min(t_i), c = \max(u_i), d = \min(u_i) \) とすると \( d(i, j) \) の最大値は次の \( 4 \) つの値を考えれば良いです。
\[ \max(d(i, j)) = \max(a – b, c – d, a – d, c – b) \]
となります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N; cin >> N; int x[N], y[N]; int t[N], u[N]; for (int i = 0; i < N; i++) { cin >> x[i] >> y[i]; t[i] = x[i] + y[i]; u[i] = x[i] - y[i]; } sort(t, t + N); sort(u, u + N); int v1 = max(t[N - 1] - t[0], u[N - 1] - u[0]); int v2 = max(t[N- 1] - u[0], u[N- 1] - t[0]); int ans = max(v1, 0); cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません