[Algorithm] cpp 백준 2261번: 가장 가까운 두 점

평면 상 N개의 점에서 가장 가까운 두 점의 제곱거리를 구합니다. x좌표로 정렬해 분할정복으로 좌·우 구간을 해결하고, y정렬 병합과 좁은 스트립에서 dy 제약으로 후보만 비교해 O(N log N)에 도달합니다. 64비트 안전, 안정 병합, dy 기반 조기 중단 등 구현 디테일까지 점검합니다.

문제

링크: https://www.acmicpc.net/problem/2261
요약: 평면에 놓인 N(≤100,000)개의 점에서 두 점 사이의 거리의 제곱이 최소가 되는 값을 구하는 문제입니다. 출력은 제곱거리 값이며, 실수 오차 없이 정수 연산으로 해결해야 합니다.

입력/출력

1
2
3
4
5
6
7
8
9
<입력>
N
x1 y1
x2 y2
...
xN yN

<출력>
가장 가까운 두 점 사이 거리의 제곱

예시

1
9

접근 개요

핵심 아이디어는 분할정복입니다. 점들을 x좌표로 정렬해 좌/우 절반으로 나눈 뒤, 각 절반의 최소 제곱거리 d를 구하고, 경계 근처(가로 거리 < √d)에 있는 점들만 y정렬된 띠(strip)에서 비교합니다.
strip은 y 오름차순으로 정렬되어 있어 한 점당 위쪽 소수의 점(이론적으로 상수 개)만 확인하면 됩니다. y 차이가 √d 이상이 되는 순간 이후는 비교를 중단할 수 있습니다.
모든 비교를 정수 제곱거리로 수행해 부동소수점 오차를 제거합니다.

알고리즘 설계

전처리: 전체 점을 x, 그다음 y로 정렬합니다.
재귀:
- 구간 크기가 2~3이면 완전탐색으로 최소 제곱거리를 계산하고, 반환 전에 해당 구간을 y기준으로 정렬해 둡니다.
- 좌/우 절반을 재귀 처리하면 두 부분 구간은 각각 y정렬 상태가 됩니다. 이를 병합 정렬 방식으로 y정렬을 유지하며 합칩니다.
- 중앙선에서 |x - midX|^2 < d를 만족하는 점들만 strip에 모으고, strip을 y정렬 상태로 순회하며 dy^2 ≥ d가 되는 지점에서 비교를 끊습니다.
자료구조: 보조 버퍼를 사용하여 y정렬 병합을 O(n)에 수행합니다.
올바름 근거: 분할정복의 표준 최근접점 정리. 좌/우 최솟값 d보다 작은 해가 존재하면 중앙선 근방 폭 √d의 띠 내부에 한 쌍이 존재하고, y정렬 상태에서 상수 개의 이웃만 보면 충분합니다.

복잡도

시간: O(N log N)
공간: O(N) (y정렬 병합용 버퍼)

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x;
    int y;
};

static inline long long squaredDistance(const Point& a, const Point& b) {
    long long dx = static_cast<long long>(a.x) - static_cast<long long>(b.x);
    long long dy = static_cast<long long>(a.y) - static_cast<long long>(b.y);
    return dx * dx + dy * dy;
}

// Recursively computes the closest pair distance squared on points[l, r),
// assuming points are sorted by x. As a side effect, points[l, r) will be
// sorted by y when the function returns.
long long closestPairRec(vector<Point>& points, vector<Point>& buffer, int l, int r) {
    int count = r - l;
    if (count <= 3) {
        long long best = LLONG_MAX;
        for (int i = l; i < r; ++i) {
            for (int j = i + 1; j < r; ++j) {
                best = min(best, squaredDistance(points[i], points[j]));
            }
        }
        sort(points.begin() + l, points.begin() + r, [](const Point& a, const Point& b) {
            if (a.y != b.y) return a.y < b.y;
            return a.x < b.x;
        });
        return best;
    }

    int mid = (l + r) / 2;
    int midX = points[mid].x;

    long long dLeft  = closestPairRec(points, buffer, l, mid);
    long long dRight = closestPairRec(points, buffer, mid, r);
    long long d = min(dLeft, dRight);

    // Merge by y to keep points[l, r) sorted by y
    int i = l, j = mid, k = l;
    while (i < mid && j < r) {
        if (points[i].y < points[j].y || (points[i].y == points[j].y && points[i].x <= points[j].x)) {
            buffer[k++] = points[i++];
        } else {
            buffer[k++] = points[j++];
        }
    }
    while (i < mid) buffer[k++] = points[i++];
    while (j < r)   buffer[k++] = points[j++];
    for (int t = l; t < r; ++t) points[t] = buffer[t];

    // Build strip: points within sqrt(d) in x from the dividing line, strip already sorted by y
    static vector<Point> strip;
    strip.clear();
    strip.reserve(r - l);
    for (int t = l; t < r; ++t) {
        long long dx = static_cast<long long>(points[t].x) - midX;
        if (dx * dx < d) strip.push_back(points[t]);
    }

    // Compare each point with subsequent points whose y-distance is < sqrt(d)
    for (size_t a = 0; a < strip.size(); ++a) {
        for (size_t b = a + 1; b < strip.size(); ++b) {
            long long dy = static_cast<long long>(strip[b].y) - strip[a].y;
            if (dy * dy >= d) break; // y too far; later points will be even farther in y
            d = min(d, squaredDistance(strip[a], strip[b]));
        }
    }
    return d;
}

long long closestPair(vector<Point>& points) {
    sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    vector<Point> buffer(points.size());
    return closestPairRec(points, buffer, 0, static_cast<int>(points.size()));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }

    cout << closestPair(points) << '\n';
    return 0;
}