[백준 2261] 가장 가까운 두 점

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

문제 분류

분할 정복, D&C

메인 아이디어

가까운 두 점의 거리의 제곱을 출력하는 함수.

go(int left, int right)

함수를 생각해보자.

[left, right] 영역에서 가장 가까운 거리는 다음과 같은 케이스 내에 있다.

1. 왼쪽 영역에서 가장 가까운 거리 → go(left, mid)
2. 오른쪽 영역에서 가장 가까운 거리 → go(mid+1, right)
3. 왼쪽 영역과 오른쪽 영역을 연결하는 점들의 거리 → ??

1과 2는 재귀 호출을 통해서 아주 간단하게 구할 수 있다. 이제 문제는 다음과 같다.

1. 입력 전처리를 어떻게 할 것인가?
2. 언제가 가장 작은 문제인가? → 직접 계산 필요.
3. 3번 케이스를 어떻게 구할 것인가? → 알고리즘 고려 필요.

입력 전처리를 어떻게 할 것인가?

x 좌표를 기준으로 정렬하자.

언제가 가장 작은 문제인가?

점이 3개 있을 때 2개 1개로 나눌 수 있을까?

나눌 수 없다. 점이 1개일 때(left == right). 거리를 정의할 수 없기 때문이다.

따라서 점이 3개 이하일 때 손수 구해주는 코드를 작성한다.

3번 케이스를 어떻게 구할 것인가?

1번 케이스와 2번 케이스의 최소 값을 d 라고 할 때, 우리는 3번 케이스에서 d 이하의 값을 찾고 있는 중이다.

따라서 생각해 볼 만한 건. 어떤 점을 비교할 때 x좌표 기준, y 좌표 기준으로 d 이상 벌어진 점은 검색할 필요도 없다는 걸 알 수 있다.

이미 좌표를 x 기준으로 정렬했기 때문에 다음과 같은 과정으로 합친다.

1. x 좌표 기준으로 mid 기준 d 이하의 점을 모은다.
2. 모은 점을 y 좌표 기준으로 정렬한다.
3. y 좌표 기준으로 d 이하로 벌어진 점을 대상으로 실제 dist를 계산한다.

코드

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<int, int> pii;

vector<pii> pts;

ll dist(pii i, pii j) {
    return (i.first - j.first) * (i.first - j.first) + (i.second - j.second) * (i.second - j.second);
}

ll go(int left, int right) {
    if (right - left + 1 <= 3) {
        ll ans = 4e18;
        for (int i = left; i <= right; i++) {
            for (int j = i + 1; j <= right; j++) {
                ans = min(ans, dist(pts[i], pts[j]));
            }
        }
        return ans;
    }

    int mid = (left + right) / 2;
    ll dl = go(left, mid), dr = go(mid + 1, right);
    ll ans = min(dl, dr);

    // 중심 기준으로 왼쪽, 오른쪽으로 d 거리 이내에 있는 친구를 찾자.
    vector<pii> psb;
    for (int i = left; i <= right; i++) {
        int d = pts[i].first - pts[mid].first;
        if (d * d < ans) {
            psb.push_back(pts[i]);
        }
    }

    sort(all(psb), [&](const pii &a, const pii &b) {
        return a.second < b.second;
    }); // y 기준으로 정렬한다.
    for (int i = 0; i < psb.size(); i++) {
        for (int j = i + 1; j < psb.size(); j++) {
            int y = psb[i].second - psb[j].second;
            if (y * y < ans) {
                ll d = dist(psb[i], psb[j]);
                ans = min(ans, d);
            } else {
                break; // 더 이동해봤자. 절대 답이 아니다. y 축을 기준으로 이미 답 범위를 넘어섬.
            }
        }
    }

    return ans;
}