9482번: 가까운 만유인력

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


$O(nlgn+min(n^2,c))$ // c: 거리가 k이하인 쌍의 최댓값

(x,y,z) 좌표계에서 각 성분을 k 만큼씩마다 나누어 버킷을 만든다. 즉, 한 성분 구간의 크기가 l이면 (l/k)^3개의 버킷이 생길 것이다.
비둘기 집의 원리에 따라 하나의 버킷 안에는 최대 O(min(n,sqrt(c)))개의 점들이 있다.
또한 이렇게 나누면 각 점들은 자신이 속한 버킷과 인접한 버킷(대각 방향도 포함)에서만 쌍 후보를 찾아도 된다.
그 밖의 버킷에는 무조건 점들 쌍의 거리가 k이상이기 때문이다.
찾을 후보의 쌍 개수는 최대 O(min(n^2,c))가 된다.

해시, 자가 균형 이진 탐색 트리, 정렬 후 이진 검색(아래 소스) 등을 이용해 특정 버킷 안의 점을 찾을 수 있을 것이다.

#include<cstdio>
#include<algorithm>
#include<vector>
#define p(x) (long long)(x)*(x)
using namespace std;
int n, k;
vector<int> v[100000];
int main() {
    while (scanf("%d%d", &n, &k) && n) {
        int r = 0;
        for (int i = 0; i < n; i++) {
            v[i].resize(6);
            for (int j = 3; j < 6; j++) scanf("%d", &v[i][j]), v[i][j - 3] = (v[i][j] += 1e9) / k;
        }
        sort(v, v + n);
        for (int i = 0; i<n; i++) {
            for (int j = 0; j<27; j++) {
                vector<int> lv = { v[i][0] + j % 3 - 1,v[i][1] + j / 3 % 3 - 1,v[i][2] + j / 9 - 1 }, uv = lv;
                uv[2]++;
                int l = lower_bound(v, v + n, lv) - v,
                    u = upper_bound(v, v + n, uv) - v;
                for (; l < u; l++) r += p(v[l][3] - v[i][3]) + p(v[l][4] - v[i][4]) + p(v[l][5] - v[i][5]) < p(k);
            }
        }
        printf("%d\n", (r - n) / 2);
    }
    return 0;
}

2261번: 가장 가까운 두 점

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

#include<stdio.h>
#include<algorithm>
#include<set>
#define x first
#define y second
using namespace std;
pair<int, int> p[100000];
set<pair<int, int> > st;
int n;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    sort(p, p + n);
    int res = 1e9, rt = sqrt(res);
    for (int i = 0, h = 0; i < n; i++) {
        while (p[i].x - p[h].x>rt) st.erase({ p[h].y, p[h++].x });
        for (set<pair<int, int> >::iterator it = st.lower_bound({ p[i].y - rt, -1e9 });
        it != st.end() && it->x <= p[i].y + rt; it++) {
            int d = (p[i].x - it->y)*(p[i].x - it->y) + (p[i].y - it->x)*(p[i].y - it->x);
            if (d < res) {
                res = d;
                rt = sqrt(d);
            }
        }
        st.insert({ p[i].y, p[i].x });
    }
    printf("%d", res);
    return 0;
}