백준 2381, 최대 거리

개요

문제 링크
골드 3, Ad hoc
50000개 점의 맨하탄 거리의 최댓값 구하기

---

접근

1. 요상한 애드혹 씹드혹 문제. 맨하탄 거리의 최댓값을 구해야 하는데, 이게 고등수학을 잘 배웠다면 크게 어렵지 않다.

2. 우리가 "한 점으로부터의 거리가 같은 점의 집합" 을 무엇이라 부르지? 바로 원이다. 이건 유클리드 거리에 대한 얘기고, 맨하탄 거리라면 한 점으로부터 거리가 같은 점의 집합은 45도 기울어진 정사각형이 된다. 즉 어떤 두점의 맨하탄 거리 = 45도 기울어진 정사각형의 한 변의 길이

3. 그럼 모든 점이 어떤 정사각형에 속하는지 찾아보고, 최대와 최소를 빼주면 끝이다. 문제에 주어진 테케를 바탕으로 보자.

   그림이 좀 많이 복잡하긴 한데, 이렇게 해주면 유클리드 거리의 최댓값이 바로 보인다. 편의상 정사각형의 한 번의 원점으로부터의 거리를 반지름이라고 하면, 보라색 사각형(5) 과 검은 사각형(7) 의 반지름의 합(12) 이 최댓값이다.

4. 따라서 왼쪽 아래에서 오른쪽 위로 가는 선들은 y=x+c 꼴이니까 y-x 또는 x-y를 저장하고, 왼쪽 위에서 오른쪽 아래로 가는 선들은 y=-x+c 꼴이니까 x+y를 저장한다. 각각의 최대 최소의 차이를 구한 뒤, 둘 중 큰 값을 출력하면 답이 된다.

---

Pseudo code

XplusY = vector(x+y)
XminusY = vector(x-y)
plusMax = max(XplusY)-min(XplusY)
minusMax = max(XminusY)-min(XminusY)
answer = max(plusMax,minusMax)

---

Source code

#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
using vec=vector<int>;
vec add,dif;
int main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    int n,x,y;
    cin>>n;
    while(n--) {
        cin>>x>>y;
        add.pb(x+y);
        dif.pb(x-y);
    }
    sort(all(add));
    sort(all(dif));
    cout<<max(add.back()-add[0],dif.back()-dif[0]);
}