추가 설명 — 왜 다음 7개만 비교하면 되는가

가장 가까운 점 쌍 ①에서 “한 점은 다음 7개만 비교하면 된다”고 했다. 왜 하필 몇 개로 끝나는지, 그림으로 천천히 따라가 보자.

---

왜 개수가 중요한가

combine 단계에서 우리는 분할선 좌우로 각각 $D$씩, 합쳐서 폭 $2D$인 밴드 안의 점들을 살핀다. 이때 한 점이 밴드 안의 모든 점과 거리를 재면, 밴드에 점이 몰린 경우 한 점당 비교가 $n$번에 달해 전체가 $O(n^2)$로 돌아간다. 분할 정복으로 얻은 이득이 사라지는 것이다.

그래서 우리에게 필요한 건 한 문장이다: “한 점은 옆의 몇 개만 보면 된다 — 그 개수는 $n$이 아무리 커져도 변하지 않는 상수다.” 이게 보장되면 combine이 가벼워지고 전체가 빨라진다. 이 글의 목표는 그 “몇 개”가 정말 상수임을, 그리고 안전한 값이 7임을 보이는 것이다.

---

직관: 가까운 점은 빽빽이 못 모인다

핵심 직관부터 잡자. 좌우를 각각 재귀로 푼 뒤, 우리는 이미 알고 있다 — 같은 편 안에서는 어떤 두 점도 $D$보다 가깝지 않다.

왜냐하면 $D = \min(D_L, D_R)$이고, $D_L$은 “왼쪽 안 두 점의 최소 거리”이기 때문이다. 즉 왼쪽 점들끼리는 적어도 $D$만큼 떨어져 있다. 오른쪽도 마찬가지다.

점들이 서로 $D$ 이상 떨어져 있다는 건, 좁은 공간에 점을 많이 욱여넣을 수 없다는 뜻이다. 의자 사이를 최소 $D$만큼 띄워야 한다면 작은 방에 의자를 몇 개밖에 못 놓는 것과 같다. 이 “몇 개밖에 못 놓는다”를 정확한 숫자로 바꾸는 것이 이 글의 전부다.

먼저, 기준점 $P$ 하나를 잡자. $P$와 거리 $D$보다 가까운 점은 어디에 있을 수 있을까?

• 같은 편에는 없다. 같은 편 점은 $P$와도 $D$ 이상 떨어져 있으니까. $P$를 중심으로 반지름 $D$인 원을 그리면 그 안에 같은 편 점은 하나도 없다.
• 반대편 밴드에서만 올 수 있다. $D$를 줄여 줄 후보는 오직 맞은편에서 온다.

---

후보는 좁은 직사각형 안에만 있다

밴드 안 점들을 y좌표 순으로 줄을 세우고, 각 점은 자기보다 위(y가 큰 쪽)에 있는 점만 본다. (아래쪽 점은 그 점이 위를 올려다볼 때 세어지므로, 한 번씩만 보면 된다.)

$P$보다 가까운 점이 있으려면 두 가지를 동시에 만족해야 한다.

• x로 가깝다 — 둘 다 밴드 안이므로 x 방향으로는 최대 $2D$(분할선 좌우 각 $D$) 안에 있다.
• y로 가깝다 — y 차이가 $D$ 이상이면 그것만으로 거리가 $D$ 이상이라 볼 필요가 없다. 그러니 y 차이는 $D$ 미만.

두 조건을 합치면, $P$ 위쪽의 후보는 가로 $2D$ · 세로 $D$ 인 직사각형 안에만 있을 수 있다.

---

칸으로 쪼개서 세기

이제 이 직사각형 안에 점이 최대 몇 개 있을 수 있는지 세면 된다. 직접 세긴 어려우니 잘게 쪼개는 트릭을 쓴다.

직사각형을 한 변이 $D/2$인 작은 정사각형 칸으로 나눈다. 가로 $2D$는 $D/2$짜리 4칸, 세로 $D$는 2칸 — 모두 8칸이다.

분할선이 칸 경계와 딱 맞아떨어지므로, 어떤 칸도 분할선을 걸치지 않는다. 각 칸은 통째로 분할선의 왼쪽이거나 오른쪽이다.

다만 분할선 위에 점이 놓이는 것까지 막을 수는 없다. x좌표가 같은 점이 여럿이면 재귀가 그 점들을 양쪽으로 나눠 갖기 때문이다. 그런 점들은 한 칸에 함께 있으면서 서로 다른 편일 수 있고, 그러면 둘 사이가 $D$ 이상이라는 보장이 없다. 그래서 「한 칸에는 점이 하나뿐」이라고 세면 안 된다.

대신 편으로 먼저 가른 뒤 센다. 어느 점이 어느 편인지는 재귀가 이미 정해 놓았으므로, 분할선 위에 점이 몇 개 있든 셈이 흐트러지지 않는다.

---

그래서 “다음 7개”

이 상수성 덕분에 combine은 점 하나당 일정한 일만 하고, 분할 정복 전체가 빠르게 돌아간다.

---

코드에서는

// 밴드 점들을 y좌표로 정렬한 뒤:
for (int i = le_idx; i <= ri_idx; i++) {
    for (int j = 1; j <= 7; j++) {       // 다음 7개만
        if (i + j > ri_idx) break;
        ll td = dist2(arr[i], arr[i + j]);
        d = min(d, td);
    }
}

안쪽 루프가 7에서 멈추는 것이 위 논거를 그대로 옮긴 것이다. 루프 안에서 y 차이를 다시 확인해 더 일찍 멈추는 구현도 있지만, 어차피 7은 상수라 점근 복잡도는 같다.

---