가장 가까운 점 쌍 ③ — Plane Sweeping과 균형 이진 탐색 트리

①·②에서 분할 정복으로 $O(n \log n)$에 닿았다. 이번엔 분할도 재귀도 없이, 점들을 왼쪽에서 오른쪽으로 한 번 훑으면서 같은 복잡도에 닿는다. 무기는 균형 이진 탐색 트리다.

입력은 점이 $n \ge 2$개라고 둔다. 「가장 가까운 점 쌍」이라는 물음이 뜻을 가지려면 쌍이 하나는 있어야 한다. 점이 하나뿐이거나 없으면 답이 정의되지 않으므로 아래 코드도 그 경우를 다루지 않는다.

---

분할 정복에서 훑기로

2편까지의 풀이는 문제를 절반으로 쪼개고, 각 절반을 푼 뒤 경계를 합쳤다. 이번엔 쪼개지 않는다. 점들을 x좌표가 작은 것부터 큰 것 순으로 한 줄로 세워 놓고, 왼쪽부터 오른쪽으로 한 점씩 훑는다. 상상 속의 수직선 하나가 왼쪽에서 오른쪽으로 쓸고 지나간다고 보면 된다. 이 수직선을 sweep line이라 부르고, 이런 접근을 Plane Sweeping(평면 훑기)이라 한다.

훑는 도중 우리는 현재까지 본 점들 사이의 최솟거리 $D$(정확히는 그 제곱 best)를 계속 들고 다닌다. 새 점 $P$를 만날 때마다 묻는다. “지금까지 본 점들 중, $P$와의 거리가 $D$보다 짧은 점이 있는가?” 있으면 $D$를 줄이고, 없으면 그대로 둔 채 다음 점으로 넘어간다. 마지막 점까지 훑고 나면 $D$가 곧 정답이다.

문제는 그 질문(“$P$보다 가까운 점이 있는가”)을 매번 $O(n)$에 훑으면 전체가 다시 $O(n^2)$이 된다는 것이다. 분할 정복에서 밴드로 후보를 좁혔듯, 여기서도 $P$와 가까울 수 있는 점을 상수 개로 가두는 장치가 필요하다.

---

활성 집합 — 폭 D의 활성 구간

$P$의 x좌표를 $x_P$라 하자. x좌표 차이가 $D$를 넘는 점은 그 차이만으로 이미 거리가 $D$ 이상이므로 $P$의 후보가 될 수 없다. 우리는 x가 작은 순으로 훑고 있으니, $P$보다 왼쪽에 있으면서 x좌표가 $x_P - D$ 이상인 점들만 후보다.

훑기가 진행되며 sweep line이 오른쪽으로 갈수록,

• 오른쪽 끝으로는 새로 만난 점 $P$가 들어오고,
• 왼쪽 끝으로는 x좌표가 $x_P - D$보다 작아진 점들이 빠져나간다.

폭 $D$짜리 활성 구간이 sweep line을 따라 오른쪽으로 미끄러지는 그림이다. 이렇게 폭이 고정된 구간을 이동시키며 양 끝에서 원소를 넣고 빼는 기법을 슬라이딩 윈도우(sliding window) 라 한다.

---

y구간도 상수 개만

x로 활성 구간을 좁혀도, 그 안에 점이 많으면 여전히 곤란하다. 여기서 두 번째 제약이 들어온다. $P$와 거리 $D$ 미만이려면 y좌표 차이도 $D$ 미만이어야 한다. 즉 후보는 y가 $[\,y_P - D,\ y_P + D\,]$인 점들뿐이다.

이는 1편에서 밴드를 셀 때 쓴 것과 같은 칸 세기 방식을, 이번엔 분할선 밴드가 아니라 sweep line 뒤의 직사각형에 적용한 것이다. “다음 7개” 보조정리와 문자 그대로 같지는 않지만, 후보 수를 상수로 묶는 같은 종류의 packing 논거다.

정리하면 새 점 $P$마다 필요한 연산은 세 가지다.

1. 활성 구간의 왼쪽 밀어내기 — x가 멀어진 점들을 활성 집합에서 삭제
2. y가 $[y_P - D,\ y_P + D]$인 점들을 조회해 $P$와 거리 비교, best 갱신
3. $P$를 활성 집합에 삽입

이 삽입·삭제·구간 조회를 빠르게 해 주는 자료구조가 균형 이진 탐색 트리다.

---

균형 이진 탐색 트리로

활성 집합에 필요한 것은 (ㄱ) 점의 삽입, (ㄴ) 점의 삭제, (ㄷ) “y좌표가 어떤 구간에 든 점만 훑기”다. 이 셋을 모두 $O(\log n)$(구간 조회는 $O(\log n +$ 조회 개수$)$)에 해내는 것이 y좌표로 정렬 상태를 유지하는 균형 이진 탐색 트리다. C++에서는 레드-블랙 트리로 구현된 std::set이 그대로 이 역할을 한다.

키는 (y, x) 쌍으로 둔다. y를 1순위로 정렬하므로 y 구간 조회가 자연스럽고, y가 같은 점들도 x로 구분돼 안전하게 공존한다.

• 구간의 시작은 lower_bound({y_P - D, -∞}) — y가 $y_P - D$ 이상인 첫 원소
• 구간의 끝은 upper_bound({y_P + D, +∞}) — y가 $y_P + D$ 이하인 마지막 원소의 다음

두 반복자 사이를 훑으면 y구간 안의 점만, 그것도 상수 개만 나온다. 트리가 어떻게 y정렬을 저절로 유지하고 이 구간을 어떻게 찾아 내려가는지는 별도 글에서 자세히 다룬다.

---

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
struct P { ll x, y; };

// 두 점 사이 거리의 제곱 (루트 회피, long long 사용)
ll dist2(const P& a, const P& b) {
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return dx * dx + dy * dy;
}

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

    int n;                  // 전제: n >= 2 (쌍이 하나는 있어야 한다)
    cin >> n;
    vector<P> pts(n);
    for (auto& p : pts) cin >> p.x >> p.y;

    // ── 훑기 순서: x좌표 오름차순 정렬 (딱 한 번) ─────────────
    sort(pts.begin(), pts.end(),
         [](const P& a, const P& b) { return a.x < b.x; });

    // ── 활성 집합: y좌표로 정렬된 균형 BST. 키는 {y, x} ──────
    set<pair<ll, ll>> active;
    ll best = LLONG_MAX;   // 현재까지 최솟거리의 제곱
    int left = 0;          // 활성 구간의 왼쪽 경계 인덱스

    active.insert({pts[0].y, pts[0].x});

    for (int i = 1; i < n; i++) {
        // ── ① 활성 구간의 왼쪽 밀어내기 ─────────────────────
        // x차이 제곱이 best를 넘은 점은 다시 후보가 될 수 없음
        while (left < i) {
            ll dx = pts[i].x - pts[left].x;
            if (dx * dx > best) {
                active.erase({pts[left].y, pts[left].x});
                left++;
            } else break;   // pts[left]가 가장 왼쪽 → 나머지는 더 가까움
        }

        // ── ② y구간 [y-D, y+D]만 조회 (D = ⌈√best⌉) ─────────
        ll D = (ll)ceill(sqrtl((long double)best));
        auto lo = active.lower_bound({pts[i].y - D, LLONG_MIN});
        auto hi = active.upper_bound({pts[i].y + D, LLONG_MAX});
        for (auto it = lo; it != hi; ++it) {
            P q{ it->second, it->first };   // 키는 {y, x} 순
            best = min(best, dist2(pts[i], q));
        }

        // ── ③ 현재 점을 활성 집합에 삽입 ────────────────────
        active.insert({pts[i].y, pts[i].x});
    }

    // best 는 최솟거리의 제곱. 실제 거리가 필요하면 sqrt(best).
    cout << best << "\n";

    return 0;
}

분할 정복 풀이(②)와의 대응:

구분	분할 정복 ②	Plane Sweeping ③
뼈대	재귀로 나누고 합침	왼쪽→오른쪽 한 번 훑기
후보 x 제약	분할선 좌우 폭 $D$ 밴드	sweep line 왼쪽 폭 $D$ 활성 구간
후보 y 제약	y정렬 후 다음 7개	트리에서 $[y-D,\ y+D]$ 구간
정렬 유지	재귀가 y정렬을 물려줌	std::set이 y정렬을 유지
핵심 자료구조	배열 + merge	균형 이진 탐색 트리

---

복잡도 — O(n log n)

이는 2편의 분할 정복과 같은 차수, 즉 정렬의 하한 $\Omega(n \log n)$에 닿는 최적이다. 분할 정복과 Plane Sweeping이 서로 다른 방식으로 같은 최적 차수에 도달한 것이다.

---