백준 2381 - 최대 거리

https://www.acmicpc.net/problem/2381

서론

이 문제에서 써야 하는 테크닉은 은근 Well-Known이라고 한다. 대회를 준비하는 사람이라면 한 번쯤 익혀둘 필요가 있다.

식 전개

서로 다른 두 점의 좌표를 각각 $(x_{i}, y_{i}), (x_{j}, y_{j})$라고 하자. 그러면 두 점의 맨해튼 거리는 $|x_{i} - x_{j}| + |y_{i} - y_{j}|$임은 너무나도 잘 알고 있다.

 

자 여기서 신기한 걸 해보자. 우리는 $max(|x_{i} - x_{j}| + |y_{i} - y_{j}|)$를 구할 건데 절댓값을 어떻게 없앨까? 절댓값을 없애기 위해 다음과 같은 전개가 가능하다.

 

$max(|x_{i} - x_{j}| + |y_{i} + y_{j}|) = max(x_{i} - x_{j}, -(x_{i} - x_{j})) + max(y_{i} - y_{j}, -(y_{i} - y_{j}))$

 

이걸 또 전개하면 엄청난 일이 벌어진다.

 

$max(x_{i} - x_{j}, -(x_{i} - x_{j})) + max(y_{i} - y_{j}, -(y_{i} - y_{j}))$

$= 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}) \}$

$= 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} \}$

 

보이는가? i와 j가 한 곳으로 묶였다!

 

그러면 우리의 일은 아주 간단해진다. $x_{i} + y_{i}, -x_{i} + y_{i}, x_{i} - y_{i}$를 구해놓고 위 식에 따라 최대 값을 찾기만 하면 된다!

주의사항

계산할 때 인덱스가 겹치는 경우를 유의하라. 계산을 위해 가장 큰 두 개의 값을 더하게 될 텐데 그 두 개의 값이 서로 같은 점을 나타내면 모순이 된다.

 

따라서 위 3가지 계산식을 인덱스와 함께 따로 저장하도록 하여 모순이 생기는 경우를 방지해야 한다. 이를 주의하며 최댓값을 구하면 된다.

 

시간 복잡도는 정렬을 해야 하므로 $O(N \log N)$

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n;
int arx[50000];
int ary[50000];
pii ar1[50000];
pii ar3[50000];
pii ar4[50000];
 
void solve()
{
  cin >> n;
  if (n == 1)
  {
    cout << 0;
    return;
  }
 
  for (int i = 0; i < n; i++)
  {
    cin >> arx[i] >> ary[i];
    ar1[i] = {arx[i] + ary[i], i};
    ar3[i] = {-arx[i] + ary[i], i};
    ar4[i] = {arx[i] - ary[i], i};
  }
 
  sort(ar1, ar1 + n);
  sort(ar3, ar3 + n);
  sort(ar4, ar4 + n);
 
  int ans = ar1[n - 1].first - ar1[0].first;
  ans = max(ans, ar1[0].first - ar1[n - 1].first);
 
  int idx = n - 1;
  if (ar4[idx].second == ar3[idx].second) --idx;
  ans = max(ans, ar4[n - 1].first + ar3[idx].first);
  idx = n - 1;
  if (ar3[idx].second == ar4[idx].second) --idx;
  ans = max(ans, ar3[n - 1].first + ar4[idx].first);
 
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록

복습하기

앳코더에서도 나온 적 있다. 복습을 위해 이것도 풀어보자.

 

https://atcoder.jp/contests/abc178/tasks/abc178_e

E - Dist Max