BOJ 2381 : 최대 거리

• 문제 링크 : boj.kr/2381
• 난이도 : G3
• 태그 : 애드 혹

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<pii> arr(n);
    for(auto &u : arr) cin >> u.first >> u.second;

    int ans = 0;
    int M = -INF, m = INF;
    for(auto u : arr) {
        M = max(M, u.first + u.second);
        m = min(m, u.first + u.second);
    }
    ans = max(ans, M-m);
    M = -INF, m = INF;
    for(auto u : arr) {
        M = max(M, u.first - u.second);
        m = min(m, u.first - u.second);
    }
    ans = max(ans, M-m);
    cout << ans;
    return 0;
}

---

풀이

좌표평면 상에서 임의의 두 점을 뽑아보자.

이 두 점을 이은 선분은 -, |, /, \ 중 한 형태로 나타날 것이다.

여기서 -와 |는 둘 /와 \ 중 하나의 형태로 표현이 가능하므로 제외할 수 있다.

a >= c라고 하면 /에서는 거리가 (a-c)+(b-d)=(a+b)-(c+d)임을 알 수 있다.

따라서 / 형태로 나타나는 두 점의 거리의 최댓값은 (x+y의 최댓값) - (x+y의 최솟값)이다.

마찬가지로 \ 형태로 나타나는 두 점의 거리의 최댓값은 (x-y의 최댓값) - (x-y의 최솟값)이다.

만약 두 경우가 섞여 한 경우에서 잘못 구했더라도 상관 없다. 한 경우에서 다른 경우의 값이 최대가 된 경우 이 두 점의 거리가 충분이 큰 것이며 다른 경우에서 올바른 거리를 구하기 때문이다.