[AtCoder - ARC121 A] 2nd Greatest Distance

난이도: 459

 

태그

• Mathematics
• Sorting

 

풀이

1. 1차원에서 생각해보자.

문제가 1차원이었다면 어떻게 풀었을까요?

 

가장 멀리 있는 두 점은 자명히 min과 max가 됩니다.

2번째로 가장 멀리 있는 두 점은 min이 한 칸 이동하거나 max가 한 칸 이동한 경우 중 더 먼 거리가 됩니다.

 

그러므로, 실질적으로 값을 비교할 때는 1, 2, N-1, N번째 값에 대해서만 비교해주면 됩니다.

// 물론 여기서 i번째 값은 정렬된 후의 i번째를 의미합니다!

 

2. [1]의 생각을 2차원으로 확장해보자.

x축의 차이와 y축의 차이 중 더 큰 값을 가지고 온다는데, 그럼 이렇게 생각해볼 수 있습니다.

 

[1]의 생각을 그냥 x축에 대해서 계산하고 y축에 대해서 계산한다면?

 

x축을 기준으로 한 1, 2, N-1, N번째의 비교 결과랑

y축을 기준으로 한 1, 2, N-1, N번째의 비교 결과만 알고 있으면

전체 결과에서 2번째로 가장 큰 값도 여기서 나오게 됩니다.

// x축을 기준으로 3등 밖이고 y축을 기준으로 3등 밖이면

// x축 + y축을 기준으로 해도 3등 밖이겠죠.

 

그러니, x축을 기준으로 1, 2, N-1, N번째를 비교하고

y축을 기준으로 1, 2, N-1, N번째를 비교해주면 됩니다.

// x축을 기준으로 비교할 때는 x축을 기준으로 정렬해줘야 합니다!
// y축도 마찬가지입니다.

 

3. 코드

inline ll f(pl2 p1, pl2 p2){
    return max(abs(p1.fr-p2.fr), abs(p1.sc-p2.sc));
}
 
pl2i arr[200020];
vector<pli2> res;
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> arr[i].fr.fr >> arr[i].fr.sc; arr[i].sc = i;
    }
    sort(arr+1, arr+n+1, [](pl2i a, pl2i b){ return a.fr.fr < b.fr.fr; });
    for (int i : {1, 2, n-1, n}){
        for (int j : {1, 2, n-1, n}){
            pl2i a = arr[i], b = arr[j];
            if (a.sc > b.sc){ swap(a, b); }
            res.push_back({ f(a.fr, b.fr), {a.sc, b.sc} });
        }
    }
    sort(arr+1, arr+n+1, [](pl2i a, pl2i b){ return a.fr.sc < b.fr.sc; });
    for (int i : {1, 2, n-1, n}){
        for (int j : {1, 2, n-1, n}){
            pl2i a = arr[i], b = arr[j];
            if (a.sc > b.sc){ swap(a, b); }
            res.push_back({ f(a.fr, b.fr), {a.sc, b.sc} });
        }
    }
    sort(all(res), [](pli2 a, pli2 b){ return a.fr > b.fr; });
    pi2 mx = res[0].sc;
    for (pli2 p : res){
        if (p.sc == mx){ continue; }
        cout << p.fr << endl; return;
    }
}