# Closest Pair Sweep

Closest Pair는 평면 위 점들 중 가장 가까운 두 점의 거리를 찾는 문제입니다. 모든 쌍을 비교하면 `O(N^2)`이지만, 점을 x좌표 순서로 훑으며 y좌표 active set을 유지하면 `O(N log N)`에 처리할 수 있습니다.

## 문제 신호

| 문제 표현 | 접근 |
| --- | --- |
| 가장 가까운 두 점 | closest pair |
| 모든 쌍 비교가 너무 크다 | sweep 또는 divide-and-conquer |
| 좌표가 정수이고 거리 제곱으로 비교 가능 | overflow 주의 |
| 동점 쌍이나 점 index 필요 | pair 복원 |

거리 비교는 제곱 거리로 해도 됩니다. 제곱근을 매번 계산할 필요가 없습니다.

## Sweep 아이디어

점을 x좌표 오름차순으로 처리합니다. 현재까지의 최단 제곱거리 `best`가 있을 때, 현재 점과 x 차이의 제곱이 `best` 이상인 오래된 점은 더 이상 후보가 될 수 없습니다.

남은 active set에서는 y좌표 차이의 제곱도 `best`보다 작은 점만 보면 됩니다.

```text
|x_i - x_j|^2 < best
|y_i - y_j|^2 < best
```

이 조건 덕분에 active set 전체가 아니라 현재 점 주변의 좁은 y 범위만 검사합니다.

## 구현

아래 구현은 가장 가까운 두 점의 제곱거리를 반환합니다.

최소 두 점을 입력하며 좌표 절댓값은 `10^9` 이하입니다. 제곱 거리는 최대 `8*10^18`이므로 작은 INF로 초기화하지 않습니다. 활성 구간의 점 사이 거리가 현재 최솟값 이상이라는 packing 성질로 후보 수가 제한되며, 전체 시간은 `O(N log N)`입니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <algorithm>
#include <cmath>
#include <stdexcept>
#include <limits>
#include <set>
#include <vector>
using namespace std;

struct Point {
    long long x;
    long long y;
    int id;
};

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

long long closestPairSquared(vector<Point> points) {
    if (points.size() < 2) throw invalid_argument("at least two points required");
    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;
    });

    long long best = squaredDistance(points[0], points[1]);
    for (int i = 1; i < (int)points.size(); ++i)
        if (squaredDistance(points[i-1], points[i]) == 0) return 0;
    set<pair<long long, int>> activeByY;
    int left = 0;

    for (int i = 0; i < (int)points.size(); ++i) {
        while (left < i) {
            long long dx = points[i].x - points[left].x;
            if (dx * dx < best) {
                break;
            }
            activeByY.erase({points[left].y, left});
            ++left;
        }

        long long limit = (long long)sqrtl((long double)best) + 1;

        auto it = activeByY.lower_bound({points[i].y - limit, -1});
        while (it != activeByY.end() && it->first <= points[i].y + limit) {
            best = min(best, squaredDistance(points[i], points[it->second]));
            ++it;
        }

        activeByY.insert({points[i].y, i});
    }

    return best;
}
```

`limit`은 `sqrtl(best) + 1`을 정수로 변환해 y축 후보 범위를 넉넉하게 잡습니다. 정확한 integer sqrt를 써도 되고, `dy * dy < best`를 loop 안에서 직접 검사해도 됩니다.

## 중복 점

같은 좌표의 점이 두 개 이상 있으면 답은 0입니다. 정렬 후 인접한 같은 점을 먼저 검사하면 빠르게 처리할 수 있습니다.

```text
if points[i].x == points[i-1].x and points[i].y == points[i-1].y:
    answer = 0
```

답이 0이면 더 줄어들 수 없으므로 즉시 종료할 수 있습니다.

## Divide-and-Conquer와 비교

Closest Pair의 표준 풀이에는 divide-and-conquer도 있습니다.

| 방식 | 장점 | 주의점 |
| --- | --- | --- |
| Sweep set | 구현이 직관적, 온라인 느낌 | set 후보 탐색과 limit 처리 |
| Divide-and-conquer | 이론적 후보 수가 명확 | y정렬 병합 구현 필요 |

둘 다 `O(N log N)`입니다. 대회에서는 구현에 익숙한 쪽을 선택하면 됩니다.

## 거리와 overflow

좌표가 `10^9`이면 차이는 `2*10^9`, 제곱은 `4*10^18`까지 갈 수 있습니다. `long long` 한계에 가까우므로 더 큰 범위에서는 `__int128`이 필요합니다.

| 좌표 범위 | 권장 |
| --- | --- |
| `|coord| <= 10^6` | `long long` 충분 |
| `|coord| <= 10^9` | `long long` 가능하지만 주의 |
| 그 이상 | `__int128` 고려 |

문제가 실제 거리 출력이면 마지막에만 `sqrt`를 적용합니다.

## 시간 복잡도

| 작업 | 시간 | 메모리 |
| --- | ---: | ---: |
| 정렬 | `O(N log N)` | `O(N)` |
| sweep set update | `O(N log N)` | active set |
| 후보 거리 검사 | 평균/기하적으로 제한 | active range |

랜덤 데이터에서는 빠르지만, 구현이 y 후보를 지나치게 넓게 보면 최악에 가까워질 수 있습니다. `dy` 범위를 반드시 제한해야 합니다.