[ boj : 1425 ] 원숭이 땅을 옮기다

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

1425번: 원숭이 땅을 옮기다

문제 : 2차원 좌표로 표현가능한 나무들이 존재합니다. 이 나무들은 밑으로도 자라서 음수길이가 가능합니다. 이때 각 나무들에 원숭이들이 위치해 있는데 원숭이들은 나무에서 나무로 점프하지 못하고 무조건 땅을 통해서 다른 위치에 있는 원숭이로 다가갈 수 있습니다.(같은 나무에 있을땐 땅을 안밟아도 됨) . 땅을 움직일 수 있습니다(x축에 평행하게)이때, 원숭이들의 거리 중에 최대값의 최소값을 구하시오

 

해설 : 문제이해부터 잘해봅시다. 디스크립션이 잘 이해가 안갈수도 있으신데 정확히 해석하면
모든 원숭이들의 쌍중에서 가장 거리가 먼 거리가 가장 작아지게 하면 됩니다
좌표의 절대값은 1e9 이하이므로 땅을 $-1e9\sim1e9$ 까지 모든 케이스를 비교해 볼 수는 없을 겁니다.

 

그러면 이분탐색을 통해 땅의 위치를 정하면 되지 않을까? 싶지만 이렇게 해서 땅의 위치를 선정한다고 한들 답을 구하려는 최대값의 최소값을 구하는데는 아무짝에 쓸모도 없는 방법입니다.

 

땅의 위치를 이분탐색으로 지정하는 것이 아닌 최대값의 최소값을 미리 가정하는 것 입니다.

즉, 우리가 구하려는 답을 그냥 미리 가정하고 이 답이 해당되는지 확인을 해보자는 뜻입니다.

 

$x$ = 최대값의 최소값 이라고 하면, x가 정해졌을때 모든 원숭이들의 쌍에 대하여 $x$이하의 거리라면 R을 좁혀주고 아니라면 L을 증가시켜 주면 됩니다.

 

그렇지만 문제가 있습니다. $x$가 정해졌더라도 결국은 땅을 어디에 위치시켜야 될지 정해야 되는데 이것이 문제가 됩니다. 서로다른 쌍을 선택했을 경우 땅의 범위가 겹치지가 않게 된다면 이는 $x$ 가 유효하지 않게 되는 것 입니다.

 

따라서 $x$가 정해지고 나서 모든 쌍의 관하여 땅의 범위가 겹치는 곳이 있어야지만 $x$ 가 유효하게 되는 것입니다.

이게 무슨말인지 이해가 잘 안가실 텐데 예시를 하나 들면

4
5 2
7 6
7 3
3 5

.......
......*
..*....
.......
......*
....*..
.......

이런 케이스가 존재할때 최대값의 최소값은 땅이 가운데에 위치한 7이 정답이 됩니다. 그러나 단순히 땅의 존재할 수 있는 여부만 확인하게 된다면 6을 도출하게 되는 것 입니다.

 

그럼 남은 건 땅의 범위를 구하는 것인데 특정 쌍에 대하여 거리가 k 이하가 되도록 하는 땅의 범위를 구하는 공식을 생각해 보면 두 원숭이의 x 좌표의 차이 와 y 좌표의 차이를 k 에서 뺀 다음 2로 나눈 거리만큼 더해지고 빼지게 됩니다.

이게 무슨뜻이냐면 $y_j<=y_i$ 일때
$$d = {k - \left\vert x_i - x_j \right\vert - \left\vert y_i - y_j \right\vert\over2}$$

 

즉, $y_j - d \sim y_i + d$ 의 땅의 범위를 갖게 되는 것 입니다.
이 범위들이 모든 쌍에 관하여 겹치는 구간이 존재한다면 이는 $x$값이 존재한다는 뜻이 되는 것이죠.

단, 예외 사항이 있는 데 바로 $d$ 값이 음수가 되는 케이스는 존재할 수가 없다는 뜻이 됩니다.
이것만 잘 걸러주면 됩니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

vector<pair<ll, ll>> v;

int solve(ll x);

int main()
{
    int n;
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++)cin >> v[i].first >> v[i].second;
    ll l = 0, r = (ll)1e10;
    ll ans = (ll)1e10;

    while (l <= r)
    {
        ll m = (l + r) / 2;
        int ret = solve(m);
        if (ret <= 0)
            l = m + 1;
        else {
            ans = m;
            r = m - 1;
        }
    }
    cout << ans;
    return 0;
}
int solve(ll x)
{
    ll l = -(ll)1e9, r=(ll)1e9;
    for(int i=0;i<v.size();i++)
        for (int j = i + 1; j < v.size(); j++) {
            ll a = x - abs(v[i].first - v[j].first) - abs(v[i].second - v[j].second);
            if (a < 0)return 0;
            a /= 2;
            ll s = min(v[i].second, v[j].second) - a;
            ll e = max(v[i].second, v[j].second) + a;
            if (e < l || r < s)return 0;
            if (l <= s && s <= r)
                l = s;
            else if (l <= e && e <= r)
                r = e;
        }
    return 1;
}