[BOJ] 2381 - 최대 거리 (C++, 애드혹/수학)

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

---

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int plus1[50001];
int minus1[50001];
int n;
int main(){
    
    cin >> n;
    for(int i=0; i<n; i++){
        int a,b;
        cin >> a >> b;
        plus1[i] = a+b;
        minus1[i] = a-b;
    }
    sort(plus1,plus1+n, greater<int>());
    sort(minus1,minus1+n, greater<int>());

    cout << max(abs(plus1[0]-plus1[n-1]), abs(minus1[0] - minus1[n-1])) << endl;
    return 0;
}

솔브닥 랜덤 마라톤 미션중에 가장 어려운 미션이길래 풀어봤다.

단순히 이중 포문으로 문제를 접근하면 시간초과가 나는 문제

좌표값의 차이를 그럼 어떻게 다뤄야 할까?

 

1. a>c, b>d인 경우 : |a-c + b-d| = a+b- (c+d)
2. a<c, b>d인 경우 : |c-a + b-d| = c-d-(a-b) = -(a-b - (c-d))
3. a>c, b<d인 경우 : |a-c + d-b| = a-b - (c-d)
4. a<c, b<d인 경우 : |c-a + d-b| = c+d - (a+b) = -(a+b - (c+d))

 

문제에서 주어진 조건을 살펴보면 위처럼 분류할 수 있다.

자세히 살펴보면, 같은 색으로 표시된 식의 결과가 부호만 바뀐채 일치하는 것을 알 수 있다.

문제에서는 절대값을 붙인 형태로 문제가 주어졌으니, 부호는 고려할 필요가 없어 1,4와 2,3은 같은 식을 가질수 있는 것이다.

그렇다면 a,b와 c,d는 한 좌표계 내에서의 값이므로 정렬을 통해 문제를 해결할 수 있다.

문제에서 요구하는 정답은 a+b의 최댓값과 c+d의 최솟값의 차, a-b의 최댓값과 c-d의 최솟값의 차를 절대값으로 표현하라는 문제로 가볍게 변한다.